Towards the Overfull Conjecture
Journal of Graph Theory · 2026-08 · 112 (4) · 370-408
DOI: 10.1002/jgt.70030 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 09.04.2026. Verfasst von Songling Shan. Die Arbeit nennt 31 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
Let be a simple graph with maximum degree denoted as . An overfull subgraph of is a subgraph satisfying the condition . In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph with maximum degree has chromatic index equal to if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial‐time algorithm for determining the chromatic index of graphs with , and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make a breakthrough towards the conjecture when not imposing a minimum degree condition on the graph: for any , there exists a positive integer such that if is a graph on vertices with , then the Overfull Conjecture holds for . The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs with . Our result also implies the Average Degree Conjecture of Vizing from 1968 for the same class of graphs .
Förderung
- National Science Foundation
Zitieren
APA
Shan, S. (2026). Towards the Overfull Conjecture. Journal of Graph Theory, 112(4), 370-408. https://doi.org/10.1002/jgt.70030
Vancouver
Shan S. Towards the Overfull Conjecture. Journal of Graph Theory. 2026;112(4):370-408. doi:10.1002/jgt.70030
BibTeX
@article{Shan2026,
author = {Shan, Songling},
title = {Towards the Overfull Conjecture},
journal = {Journal of Graph Theory},
year = {2026},
volume = {112},
number = {4},
pages = {370--408},
doi = {10.1002/jgt.70030}
}
EUVIMED