The optimal \chi-bound for (P₇,C₄,C₅)-free graphs

DOI10.1016/J.DISC.2024.114036arXiv2212.05239MaRDI QIDQ6420122FDOQ6420122

Shenwei Huang

Publication date: 10 December 2022

Abstract: In this paper, we give an optimal $chi$-binding function for the class of $(P_7,C_4,C_5)$-free graphs. We show that every $(P_7,C_4,C_5)$-free graph $G$ has $chi(G)lelceilfrac119omega(G)ceil$. To prove the result, we use a decomposition theorem obtained in [K. Cameron and S. Huang and I. Penev and V. Sivaraman, The class of $(P_7,C_4,C_5)$-free graphs: Decomposition, algorithms, and $chi$-boundedness, Journal of Graph Theory 93, 503--552, 2020] combined with careful inductive arguments and a nontrivial use of the K"{o}nig theorem for bipartite matching.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cited In (1)

• Structure of some \(( P_7, C_4)\)-free graphs with application to colorings

This page was built for publication: The optimal $\chi$-bound for $(P_7,C_4,C_5)$-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420122)