The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs
We prove the Borodin--Kostochka conjecture for $(\mathrm{diamond},L_4)$-free graphs and $(\mathrm{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 $χ=Δ$.
Authors
- Alireza Fiujlaali (ORCID: https://orcid.org/0009-0008-6855-8824)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-10-29
- DOI
- https://doi.org/10.48550/arxiv.2610.40279
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint