The optimal $χ$-bound for $\{P_6, \text{dart}, K_4\}$-free graphs

Yidong Zhou; Kaiyang Lan

paper

The optimal $χ$ -bound for ${P_{6}, dart, K_{4}}$ -free graphs

arXiv:2607.14667

Abstract

A \textit{diamond} is a graph obtained from $K_4$ by removing an edge, and a \textit{dart} is a graph obtained from a diamond by adding a pendant edge to a vertex of degree 3. We prove that every ${P_{6}, dart, K_{4}}$ -free graph is 6-colorable. This improves the previous bound of 7 due to Hong and Xu \cite{HongXu2025} and resolves their open question on the optimality of the bound. Our result also extends a theorem of Karthick and Mishra~\cite{KarthickMishra2018}, who proved 6-colorability for the class of $\{P_6, \text{diamond}, K_4\}$-free graphs.

arXiv comment10 pages, comments are welcome

The optimal χ-bound for {P6​,dart,K4​}-free graphs

Abstract

The optimal $χ$ -bound for ${P_{6}, dart, K_{4}}$ -free graphs