Coloring (P₆, diamond, K₄)-free graphs

2017/03/02 by Karthick, T., Mishra, Suchismita
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1703.00606

Abstract

We show that every (P₆, diamond, K₄)-free graph is 6-colorable. Moreover, we give an example of a (P₆, diamond, K₄)-free graph G with χ(G) = 6. This generalizes some known results in the literature.

Related

• The optimal χ-bound for \P₆, dart, K₄\-free graphs
• Colouring graphs with no induced six-vertex path or diamond
• Square-free graphs with no six-vertex induced path
• 4-coloring (P₆, bull)-free graphs
• 4-coloring P₆-free graphs with no induced 5-cycles