Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 24 min ago
PreprintarXiv licencearXiv

The chromatic number of {ISK4, textupdiamond}-free graphs

  • Qing Cui
  • Kaiyang Lan
Open at sourcePDFDOICite

Abstract

An ISK4 is a graph that is isomorphic to a subdivision of K4; a \textit{diamond} is K4 minus one edge; and a \textit{bowtie} consists of two triangles sharing exactly one vertex. Lévêque, Maffray, and Trotignon~(2012) conjectured that every ISK4-free graph is $4$-colorable. Chen, Chen, Cui, Feng, and Liu~(2021) proved this for {textupdiamond,textupbowtie}-free graphs. We prove this conjecture for diamond-free graphs. Moreover, the bound is optimal.

Related

  1. Geometric triangle-free graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  2. Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
    Saieed Akbari, Arash Beikmohammadi
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  4. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Box-Delaunay graphs of large chromatic number
    István Tomon
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{cui2026chromatic,
  title = {{The chromatic number of $\\mathrmISK_4, \textupdiamond\$-free graphs}},
  author = {Qing Cui and Kaiyang Lan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.32404},
  eprint = {2610.32404},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.32404},
}
RIS
TY  - UNPB
TI  - The chromatic number of {ISK_4, textupdiamond}-free graphs
AU  - Qing Cui
AU  - Kaiyang Lan
PY  - 2026
DA  - 2026/10/23
PB  - arXiv
DO  - 10.48550/arxiv.2610.32404
UR  - https://arxiv.org/abs/2610.32404
AB  - An ISK_4 is a graph that is isomorphic to a subdivision of K_4; a \textit{diamond} is K_4 minus one edge; and a \textit{bowtie} consists of two triangles sharing exactly one vertex. Lévêque, Maffray, and Trotignon~(2012) conjectured that every ISK_4-free graph is $4$-colorable. Chen, Chen, Cui, Feng, and Liu~(2021) proved this for {textupdiamond,textupbowtie}-free graphs. We prove this conjecture for diamond-free graphs. Moreover, the bound is optimal.
ER  -