4-colorability of \(P_6\)-free graphs

DOI10.1016/j.endm.2015.06.007zbMath1346.05060OpenAlexW2200236463MaRDI QIDQ322185

Ingo Schiermeyer, Christoph Brause, Petr Vrána, Přemysl Holub, Rastislav Krivoš-Belluš, Zdeněk Ryjáček

Publication date: 14 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.06.007

zbMATH Keywords

(\(P_6\), bull, \(Z_2\))-free graphs(\(P_6\), bull, kite)-free graphs(\(P_6\), chair)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Some results on graphs without long induced paths
• The complexity of colouring problems on dense graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Vertex colouring and forbidden subgraphs -- a survey
• Three complexity results on coloring \(P_k\)-free graphs
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles

This page was built for publication: 4-colorability of \(P_6\)-free graphs