K. Kawarabayashi

collaborators

6 papers

math.CO2026

Three-edge-coloring apex cubic graphs

Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo +3

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G - v$ is planar. We prove that every $2$ -connected apex cubic graph is three-edge-colorable. This result gives the fina…

cs.DS2026

The Balanced Four-Color Theorem

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We show that every planar graph with $n \geq 3$ vertices admits a 4-coloring in which each color is used on fewer than $n /2$ vertices. This bound is the best possible. Moreover, su…

math.CO2026

Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture

Ken-ichi Kawarabayashi, Gexin Yu

For a given subset $S \subseteq V (G)$ of a graph $G$ , the pair $(G, S)$ is \emph{knitted} if for every partition of $S$ into non-empty subsets $S_{1}, S_{2}, \dots, S_{t}$ , there exist pa…

cs.DS2025

Online Graph Coloring for $k$ -Colorable Graphs

Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda

We study the problem of online graph coloring for $k$ -colorable graphs. The best previously known deterministic algorithm uses $O (n^{1 - \frac{1}{k !}})$ colors for genera…

math.CO2025

5-Coloring Planar Graphs with a Color Class of Order at Most $∣ V ∣/6$

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita

We show that any planar graph $G = (V, E)$ has a 5-coloring such that one color class contains at most $∣ V ∣/6$ vertices. In other words, there exists a partition of $V$ 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…