The optimal $χ$-bound for $\{P_6, \text{dart}, K_4\}$-free graphs
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, \text{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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.14667
curl -X POST /api/v1/records/arxiv/2607.14667/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.14667/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'