Paperlane

no. 7 · Tuesday 3 November 2026

An optimal $χ$-bound for $\{P_7, \text{diamond}\}$-free graphs

Kaiyang Lan and Hongyang Wang

math.CO · 28 pp

Abstract

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.

comments
28 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.03083 ↗