Zpět
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