We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed
graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a …

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properly (h-1)-colourable.
We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_h …

Given two graphs $ H $ and $ G $, the Subgraph Isomorphism problem asks if $ H $ is
isomorphic to a subgraph of $ G $. While NP-hard in general, algorithms exist for various …

We prove that there is a randomized polynomialtime algorithm that given an edge-weighted
graph G excluding a fixed-minor Q on n vertices and an accuracy parameter ε\gt 0 …

For p∈ N, a coloring λ of the vertices of a graph G is p-centered if for every connected
subgraph H of G, either H receives more than p colors under λ or there is a color that …

We prove that any graph excluding a fixed minor can have its edges partitioned into a
desired number k of color classes such that contracting the edges in any one color class …

Distributed network optimization problems, such as minimum spanning tree, minimum cut,
and shortest path, are an active research area in distributed computing. This paper presents …

We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-
minor-free graph G contains a path of length k in 2O (k)⋅ nO (1) steps. Our approach builds …

The Bipartite Contraction problem takes as input an n-vertex graph G and an integer k, and
the task is to determine whether we can obtain a bipartite graph from G by a sequence of at …

A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result
that every graph $ G $ with no minor isomorphic to a fixed graph $ H $ has a certain …