EUVIMEDEUVIMED entdecken
Crossref

5-Coloring Planar Graphs with a Color Class of Order at Most \(|V|/6\)

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita

SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1107-1122

DOI: 10.1137/25m1786362 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 21.07.2026. Verfasst von Yuta Inoue und 2 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Gefördert von: Japan Science and Technology Agency.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that any planar graph [Formula: see text] has a 5-coloring such that one color class contains at most [Formula: see text] vertices. In other words, there exists a partition of [Formula: see text] into five independent sets [Formula: see text] such that [Formula: see text]. Our proof yields an [Formula: see text]-time algorithm to find such a partition, and unlike the Four Color Theorem, our proof is fully verifiable without computer assistance.

Förderung

  • Japan Science and Technology Agency

Zitieren

APA

Inoue, Y., Kawarabayashi, K., & Miyashita, A. (2026). 5-Coloring Planar Graphs with a Color Class of Order at Most \(|V|/6\). SIAM Journal on Discrete Mathematics, 40(3), 1107-1122. https://doi.org/10.1137/25m1786362

Vancouver

Inoue Y, Kawarabayashi K, Miyashita A. 5-Coloring Planar Graphs with a Color Class of Order at Most \(|V|/6\). SIAM Journal on Discrete Mathematics. 2026;40(3):1107-1122. doi:10.1137/25m1786362

BibTeX
@article{Inoue2026,
  author = {Inoue, Yuta and Kawarabayashi, Ken-ichi and Miyashita, Atsuyuki},
  title = {5-Coloring Planar Graphs with a Color Class of Order at Most \(|V|/6\)},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2026},
  volume = {40},
  number = {3},
  pages = {1107--1122},
  doi = {10.1137/25m1786362}
}
Kostenlos starten →