Přejít k obsahu


4-colorability of P(6)-free graphs

Citace:
BRAUSE, C., SCHIERMEYER, I., HOLUB, P., RYJÁČEK, Z., VRÁNA, P., KRIVOŠ-BELLUŠ, R. 4-colorability of P(6)-free graphs. Electronic Notes in Discrete Mathematics, 2015, roč. 49, č. listopad 2015, s. 37-42. ISSN: 1571-0653
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: 4-colorability of P(6)-free graphs
Rok vydání: 2015
Autoři: Christoph Brause , Ingo Schiermeyer , RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Mgr. Petr Vrána Ph.D. , Rastislav Krivoš-Belluš
Abstrakt CZ: V článku se zabýváme výpočetní složitostí study problému 4-obarvitelnosti v podtřídách třídy grafů bez P(6). Je obecně známo, že problém 4-obarvitelnosti je v obecnosti NP-úplný. Huang nedávno publikoval hypotézu, že problém 4-obarvitelnosti je polynomiální v třídě grafů bez P(6). V článku ověřujeme hypotézu pro podtřídy grafů bez indukovaných podgrafů typu (P(6), bull, Z(2)), (P(6), bull, kite) a (P(6), chair).
Abstrakt EN: In this paper, we study complexity of the 4-colorability in subclasses of P(6)-free graphs. It is well-known that the 4-colorability problem is NP-complete in general. Recently, Huang conjectured that 4-colorability of P(6)-free graphs can be decided in polynomial time. We show that this conjecture is true for the classes of (P(6), bull, Z(2))-free graphs, (P(6), bull, kite)-free graphs, and (P(6), chair)-free graphs.
Klíčová slova

Zpět

Patička