5-Coloring Planar Graphs with a Color Class of Order at Most \(|V|/6\)
Abstract
Abstract. 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.
Fields of Study & Subjects
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Limits and Structures in Graph Theory
Publication details
- Journal / source
- SIAM Journal on Discrete Mathematics
- Volume
- 40
- Issue
- 3
- Pages
- 1107–1122
- Publication date
- 21 July 2026
- Language
- EN