3 citations · 4 across the 13 of their papers we have counts for
14 papers
A directed flat wall theorem excluding a crossrow grid
Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
The graph minor project contains the most influential results in recent undirected graph theory research. There has been progress in recent years in generalising some of their resu…
Coloring digraphs with colors
Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta
The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possib…
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain +33
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks,…
A quasi-polynomial bound for the minimal excluded minors for a surface
Sarah Houdaigoui, Ken-ichi Kawarabayashi
As part of their graph minor project, Robertson and Seymour showed in 1990 that the class of graphs that can be embedded in a given surface can be characterized by a finite set of…
Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that for every surface , the class of Eulerian directed graphs that are Eulerian embeddable into (in particular they have degree at most ) is well-quasi-ordered…
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…
-dicolouring of digraphs
Ararat Harutyunyan, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta +1
In 1977, Borodin and Kostochka conjectured that every graph with maximum degree is -colourable, unless it contains a clique of size . In 1999, Reed confirmed th…
Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani +1
In the Vertex Disjoint Paths with Congestion problem, the input consists of a digraph , an integer and pairs of vertices , and the task is to find a set of p…
Edge-colouring and orientations: applications to degree- and -boundedness
Arnab Char, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta
We prove a new generalisation of Ramsey's theorem by showing that every -edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph who…
An analogue of Reed's conjecture for digraphs
Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta
Reed in 1998 conjectured that every graph satisfies . As a partial result, he proved the existence of for which…
Edge-Disjoint Paths in Eulerian Digraphs
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
Disjoint paths problems are among the most prominent problems in combinatorial optimization. The edge- as well as vertex-disjoint paths problem, are NP-complete on directed and und…
Packing even directed circuits quarter-integrally
Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer +1
We prove the existence of a computable function such that for every integer and every digraph either contains a collection of…
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem
Koji Ichikawa, Shinji Ito, Daisuke Hatano +4
We consider the sparse contextual bandit problem where arm feature affects reward through the inner product of sparse parameters. Recent studies have developed sparsity-agnostic al…
K_6 minors in large 6-connected graphs
Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas +1
Jorgensen conjectured that every 6-connected graph with no K_6 minor has a vertex whose deletion makes the graph planar. We prove the conjecture for all sufficiently large graphs.