3 citations · 8 across the 15 of their papers we have counts for
16 papers · 1 filter
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 sa…
Line-width and path-width
Tung Nguyen, Alex Scott, Paul Seymour
For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does n…
Asymptotic structure. VI. Distant paths across a disc
Tung Nguyen, Alex Scott, Paul Seymour
Menger's theorem says that, for , if are sets of vertices in a graph , then either there are vertex-disjoint paths between and , or there is a set X…
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…
Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
Tung Nguyen, Alex Scott, Paul Seymour
Coarse graph theory concerns finding 'coarse' analogues of graph theory theorems, replacing disjointness with being far apart. One of the most interesting open questions is to find…
The vertex sets of subtrees of a tree
Maria Chudnovsky, Tung Nguyen, Alex Scott +1
Let be a set of subsets of a set . When is there a tree with vertex set such that each member of is the set of vertices of a subtree of ?…
Asymptotic structure. I. Coarse tree-width
Tung Nguyen, Alex Scott, Paul Seymour
In this paper, we develop a coarse analogue of tree-width. We prove that a graph admits a tree-decomposition in which each bag is contained in the union of a bounded number of…
Distant digraph domination
Tung Nguyen, Alex Scott, Paul Seymour
A {\em -kernel} in a digraph is a stable set of vertices such that every vertex of can be joined from by a directed path of length at most . We prove three re…
Subdivisions and near-linear stable sets
Tung Nguyen, Alex Scott, Paul Seymour
We prove that for every complete graph , all graphs with no induced subgraph isomorphic to a subdivision of have a stable subset of size at least $|G|/{\rm polylog}|…
Trees and near-linear stable sets
Tung Nguyen, Alex Scott, Paul Seymour
When is a forest, the Gyárfás-Sumner conjecture implies that every graph with no induced subgraph isomorphic to and with bounded clique number has a stable set of linea…
Graphs without a 3-connected subgraph are 4-colorable
Édouard Bonnet, Carl Feghali, Tung Nguyen +4
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…
A counterexample to the coarse Menger conjecture
Tung Nguyen, Alex Scott, Paul Seymour
Menger's well-known theorem from 1927 characterizes when it is possible to find vertex-disjoint paths between two sets of vertices in a graph . Recently, Georgakopoulos and…
Induced subgraph density. VI. Bounded VC-dimension
Tung Nguyen, Alex Scott, Paul Seymour
We confirm a conjecture of Fox, Pach, and Suk, that for every , there exists such that every -vertex graph of VC-dimension at most has a clique or stable set of s…
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 o…
A shorter proof of the path-width theorem
P. Seymour
A graph has {\em path-width} at most if it can be built from a sequence of graphs each with at most vertices, by overlapping consecutive terms. Every graph with path-widt…