970 citations · 1.7k across the 49 of their papers we have counts for
18 papers · 1 filter
Decomposition of (infinite) digraphs along directed 1-separations
Nathan Bowler, Florian Gut, Meike Hatzel +3
We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the s…
A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi +2
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does n…
Quickly excluding a non-planar graph
Ken-ichi Kawarabayashi, Robin Thomas, Paul Wollan
A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph with no minor isomorphic to a fixed graph has a certain structure.…
Automorphism groups of maps in linear time
Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela +1
By a map we mean a -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can…
A half-integral Erdős-Pósa theorem for directed odd cycles
Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon +1
We prove that there exists a function such that every directed graph contains either directed odd cycles where every vertex of is c…
Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
Vida Dujmović, Ken-ichi Kawarabayashi, Bojan Mohar +1
The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph that does not contain a fixed grap…