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
We show that every planar graph with vertices admits a 4-coloring in which each color is used on fewer than vertices. This bound is the best possible. Moreover, su…
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 handl…
An almost quadratic bound for the minimal excluded minors for a surface
Sarah Houdaigoui, Ken-ichi Kawarabayashi
As part of the graph minor project, Robertson and Seymour showed in 1990 that the class of graphs embeddable in a given surface can be characterized by a finite set of minimal excl…
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…
Online Graph Coloring for -Colorable Graphs
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
We study the problem of online graph coloring for -colorable graphs. The best previously known deterministic algorithm uses colors for genera…
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…
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…
Better coloring of 3-colorable graphs
Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda
We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In thi…
Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +2
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In o…