EUVIMEDEUVIMED entdecken
Crossref

Towards the Overfull Conjecture

Songling Shan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →