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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

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

Alireza Fiujlaali
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

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

Alireza Fiujlaali
preprint en

Abstract

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 $χ=Δ$.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
The Borodin--Kostochka Conjecture for Two Classes of Diamond-Free Graphs — Alireza Fiujlaali · arXiv (Cornell University) (2026) | TGRS Research Map | TGRS