4-colorability of P₆-free graphs

DOI10.1016/J.ENDM.2015.06.007zbMATH Open1346.05060OpenAlexW2200236463MaRDI QIDQ322185FDOQ322185

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

Publication date: 14 October 2016

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

Recommendations

• Four-coloring \(P_6\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• Complexity of coloring graphs without paths and cycles

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• 4-coloring \((P_6, \text{bull})\)-free graphs
• On the chromatic number of (\(P_6\), diamond)-free graphs
• \((2P_2,K_4)\)-free graphs are 4-colorable
• Obstructions for three-coloring graphs without induced paths on six vertices
• Characterization of \(P_{6}\)-free graphs
• A new characterization of \(P_{6}\)-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• \(P_4\)-colorings and \(P_4\)-bipartite graphs
• Four-coloring \(P_6\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322185)