3 papers
math.CO2026
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3
We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be ach…
math.CO2025
5-Coloring Planar Graphs with a Color Class of Order at Most
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita
We show that any planar graph has a 5-coloring such that one color class contains at most vertices. In other words, there exists a partition of into five inde…
math.CO2025
Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +2
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exceptional graph class called "Petersen-like", is 3-edge-colorable. This me…