Skip to content
DraconiticResearch
Search Sources API
190,869 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

Elementary graphs are chromatic-choosable

  • Narayanan N
  • Nandana K. Vasudevan
  • K. Somasundaram
Open at sourcePDFDOICite

Abstract

A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph G satisfies ch(G)=χ(G)=ω(G), confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.

Related

  1. Claw-free perfect graphs are chromatic-choosable
    Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Cones of Theta Graphs are Enumeratively Chromatic-Choosable
    Kingston Barnes, Vincent Fesenmeier, Braxton Gaither +7
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An elementary proof of a tight Δ+1 bound for the additive chromatic number
    Alex Koutsoutis, Joseph Koutsoutis
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  5. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{narayanan2026elementary,
  title = {{Elementary graphs are chromatic-choosable}},
  author = {Narayanan N and Nandana K. Vasudevan and K. Somasundaram},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16258},
  eprint = {2610.16258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16258},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Elementary graphs are chromatic-choosable
AU  - Narayanan N
AU  - Nandana K. Vasudevan
AU  - K. Somasundaram
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16258
UR  - https://arxiv.org/abs/2610.16258
AB  - A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph G satisfies ch(G)=χ(G)=ω(G), confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.
ER  -