970 citations · 1.7k across the 49 of their papers we have counts for
7 papers · 1 filter
The canonical directed tree decomposition and its applications to the directed disjoint paths problem
Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The canonical tree-decomposition theorem, given by Robertson and Seymour in their seminal graph minors series, turns out to be one of the most important tool in structural and algo…
Additive non-approximability of chromatic number in proper minor-closed classes
Zdeněk Dvořák, Ken-ichi Kawarabayashi
Robin Thomas asked whether for every proper minor-closed class C, there exists a polynomial-time algorithm approximating the chromatic number of graphs from C up to a constant addi…
The Erdos-Posa Property for Directed Graphs
Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Stephan Kreutzer +1
A classical result by Erdos and Posa states that there is a function such that for every , every graph contains pairwise vertex…
The Directed Grid Theorem
Ken-ichi Kawarabayashi, Stephan Kreutzer
The grid theorem, originally proved by Robertson and Seymour in Graph Minors V in 1986, is one of the most central results in the study of graph minors. It has found numerous appli…
Edge-colouring seven-regular planar graphs
Maria Chudnovsky, Katherine Edwards, Ken-ichi Kawarabayashi +1
A conjecture due to the fourth author states that every -regular planar multigraph can be -edge-coloured, provided that for every odd set of vertices, there are at least…
Combinatorial coloring of 3-colorable graphs
Ken-ichi Kawarabayashi, Mikkel Thorup
We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to $\tO(n^{4/11})$ col…