From the 1 of 10 linked papers with an AI index.
12 papers
Three-edge-coloring apex cubic graphs
Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo +3
A graph is \emph{apex} if has a vertex such that is planar. We prove that every -connected apex cubic graph is three-edge-colorable. This result gives the fina…
The Balanced Four-Color Theorem
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
The paper proves that every planar graph with at least three vertices can be 4‑colored so that each color class contains fewer than half of the vertices, and provides an O(n log n)…
Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture
Ken-ichi Kawarabayashi, Gexin Yu
For a given subset of a graph , the pair is \emph{knitted} if for every partition of into non-empty subsets , there exist pa…
Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that every class of Eulerian directed graphs of bounded carving width (equivalently of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we…
EPTAS for Hard Graph Cut Problems for Dense Graphs
Kaisei Deguchi, Ken-ichi Kawarabayashi, Hiroaki Mori
Everywhere--dense graphs are defined as graphs on vertices in which every vertex has degree at least for some constant . Approximation schemes are vital for ha…
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…