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