The optimal χ-bound for \P₆, dart, K₄\-free graphs

2026/07/16 by Yidong Zhou, Kaiyang Lan
#math.CO

paper · pdf

Abstract

A diamond is a graph obtained from \(K₄\) by removing an edge, and a dart is a graph obtained from a diamond by adding a pendant edge to a vertex of degree 3. We prove that every \P₆, dart, K₄\-free graph is 6-colorable. This improves the previous bound of 7 due to Hong and Xu \citeHongXu2025 and resolves their open question on the optimality of the bound. Our result also extends a theorem of Karthick and Mishra~\citeKarthickMishra2018, who proved 6-colorability for the class of \(\P₆, diamond, K₄\\)-free graphs.

Related

• Coloring (P₆, diamond, K₄)-free graphs
• An Optimal χ-Bound for (P₆, diamond)-Free Graphs
• Colouring graphs with no induced six-vertex path or diamond
• Square-free graphs with no six-vertex induced path
• Colouring Diamond-free Graphs