4-coloring $P_6$-free graphs with no induced 5-cycles

Abstract

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_5$ and no induced 6-vertex path $P_6$.

References in corpus (3)

• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Improved Complexity Results on $k$-Coloring $P_t$-Free Graphs
• Narrowing the Complexity Gap for Colouring ($C_s$,$P_t$)-Free Graphs

Cited by in corpus (3)

• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• 4-coloring ($P_6$, bull)-free graphs