Skip to content
DraconiticResearch
Search Sources API
179,152 studies31 sourcesUpdated 52 min ago
PreprintarXiv licencearXiv

An optimal χ-bound for {P7, diamond}-free graphs

  • Kaiyang Lan
  • Hongyang Wang
Open at sourcePDFDOICite

Abstract

A diamond is a graph obtained by removing an edge from the complete graph on four vertices. A graph is {P7, diamond}-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)≤ω(G)+c for every {P7, diamond}-free graph G. We answer this question affirmatively by proving χ(G) ≤ ω(G)+3. Moreover, the bound is optimal.

Related

  1. The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs
    Alireza Fiujlaali
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The chromatic number of {ISK4, textupdiamond}-free graphs
    Qing Cui, Kaiyang Lan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A sharp bound on the binding number of Kk-free graphs and the Brandt conjecture
    Jifu Lin, Heng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A quasi-polynomial χ-bound for P6-free graphs
    Shenwei Huang, Yidong Zhou, Yuwen Zhou
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs
    Dongxiu Cai, Zhengbo Chen, Xiao-Dong Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lan2026optimal,
  title = {{An optimal $χ$-bound for $\P_7, \textdiamond\$-free graphs}},
  author = {Kaiyang Lan and Hongyang Wang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03083},
  eprint = {2611.03083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03083},
}
RIS
TY  - UNPB
TI  - An optimal χ-bound for {P_7, diamond}-free graphs
AU  - Kaiyang Lan
AU  - Hongyang Wang
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03083
UR  - https://arxiv.org/abs/2611.03083
AB  - A diamond is a graph obtained by removing an edge from the complete graph on four vertices. A graph is {P_7, diamond}-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)≤ω(G)+c for every {P_7, diamond}-free graph G. We answer this question affirmatively by proving χ(G) ≤ ω(G)+3. Moreover, the bound is optimal.
ER  -