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

The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs

  • Alireza Fiujlaali
Open at sourcePDFDOICite

Abstract

We prove the Borodin--Kostochka conjecture for (diamond,L4)-free graphs and (diamond,K5+)-free graphs, where L4 is obtained from K4 by attaching a path of length two to one clique vertex, and K5+ is obtained from K5 by adding a vertex adjacent to exactly one clique vertex. The proof uses structural properties of maximum cliques in diamond-free vertex-critical graphs with χ=Δ.

Related

  1. The Borodin--Kostochka inequality from degree 750
    Lizhong Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The chromatic number of {ISK4, textupdiamond}-free graphs
    Qing Cui, Kaiyang Lan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. An optimal χ-bound for {P7, diamond}-free graphs
    Kaiyang Lan, Hongyang Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Erdős--Straus Conjecture: Modular Inversion in Mordell Classes
    Andres Ventas
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. Non-isomorphic graphs have distinct vertex-Ramsey classes
    Maria Axenovich, Patrick Schmitteckert
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{fiujlaali2026borodinkostochka,
  title = {{The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs}},
  author = {Alireza Fiujlaali},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40279},
  eprint = {2610.40279},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40279},
}
RIS
TY  - UNPB
TI  - The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs
AU  - Alireza Fiujlaali
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40279
UR  - https://arxiv.org/abs/2610.40279
AB  - We prove the Borodin--Kostochka conjecture for (diamond,L_4)-free graphs and (diamond,K_5^+)-free graphs, where L_4 is obtained from K_4 by attaching a path of length two to one clique vertex, and K_5^+ is obtained from K_5 by adding a vertex adjacent to exactly one clique vertex. The proof uses structural properties of maximum cliques in diamond-free vertex-critical graphs with χ=Δ.
ER  -