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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

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

Kaiyang Lan, Hongyang Wang
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

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

Kaiyang Lan, Hongyang Wang
preprint en

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.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
An optimal $χ$-bound for $\{P_7, \text{diamond}\}$-free graphs — Kaiyang Lan, Hongyang Wang · arXiv (Cornell University) (2026) | TGRS Research Map | TGRS