15 papers
Asymptotic structure. III. Excluding a fat tree
Tung Nguyen, Alex Scott, Paul Seymour
Robertson and Seymour proved that for every finite tree , there exists such that every finite graph with no minor has path-width at most ; and conversely, for eve…
Asymptotic structure. V. The coarse Menger conjecture in bounded path-width
Alex Divoux, Tung Nguyen, Alex Scott +1
Menger's theorem tells us that if are sets of vertices in a graph , then (for ) either there are vertex-disjoint paths between and , or there is a set…
Induced subgraph density. IV. New graphs with the ErdÅs-Hajnal property
Tung Nguyen, Alex Scott, Paul Seymour
ErdÅs and Hajnal conjectured that for every graph , there exists such that every -free graph has a clique or a stable set of size at least (a graph is -…
Induced subgraph density. VII. The five-vertex path
Tung Nguyen, Alex Scott, Paul Seymour
We prove the ErdÅs-Hajnal conjecture for the five-vertex path ; that is, there exists such that every -vertex graph with no induced has a clique or stable set…
On polynomially high-chromatic pure pairs
Tung H. Nguyen
Let be a forest. We study polynomially high-chromatic pure pairs in graphs with no as an induced subgraph (-free graphs in other words), with applications to the polynom…
Asymptotic structure. II. Path-width and additive quasi-isometry
Tung Nguyen, Alex Scott, Paul Seymour
We show that if a graph admits a quasi-isometry to a graph of bounded path-width, then we can assign a non-negative integer length to each edge of , such that the s…