An optimal $χ$-bound for $\{P_7, \text{diamond}\}$-free graphs
A $\textit{diamond}$ is a graph obtained by removing an edge from the complete graph on four vertices. A graph is $\{P_7, \text{diamond}\}$-$\textit{free}$ if it contains no induced subgraph isomorphic to a seven-vertex path or a diamond. Schiermeyer (2020) asked whether there is a constant $c$ such that $χ(G)\leqω(G)+c$ for every $\{P_7, \text{diamond}\}$-free graph $G$. We answer this question affirmatively by proving $χ(G) \leq ω(G)+3$. Moreover, the bound is optimal.
Authors
- Kaiyang Lan (ORCID: https://orcid.org/0000-0002-2739-9053)
- Hongyang Wang
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-02
- DOI
- https://doi.org/10.48550/arxiv.2611.03083
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint