4-coloring P₆-free graphs with no induced 5-cycles

2014/07/09 by Chudnovsky, Maria, Maceli, Peter, Stacho, Juraj +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1407.2487

Abstract

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C₅ and no induced 6-vertex path P₆.

Related

• 4-coloring (P₆, bull)-free graphs
• Four-coloring P₆-free graphs. I. Extending an excellent precoloring
• Four-coloring P₆-free graphs. II. Finding an excellent precoloring
• Improved Complexity Results on k-Coloring P_t-Free Graphs
• (2P₂,K₄)-Free Graphs are 4-Colorable