Tung H. Nguyen

activity

20212026

most citedInduced subgraph density. VII. The five-vertex path

3 citations · 15 across the 29 of their papers we have counts for

collaborators

32 papers

math.CO2026

On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs

Tung Nguyen, Bartosz Walczak

A well-known problem of Erdős and Hajnal from the 1960s asks whether every graph with huge chromatic number contains a subgraph with large girth and large chromatic number. Very re…

math.CO2025

Asymptotic structure. II. Path-width and additive quasi-isometry

Tung Nguyen, Alex Scott, Paul Seymour

We show that if a graph $G$ admits a quasi-isometry $ϕ$ to a graph $H$ of bounded path-width, then we can assign a non-negative integer length to each edge of $H$ , such that the sa…

math.CO2025

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…

math.CO2025

Asymptotic structure. VI. Distant paths across a disc

Tung Nguyen, Alex Scott, Paul Seymour

Menger's theorem says that, for $k \geq 0$ , if $S, T$ are sets of vertices in a graph $G$ , then either there are $k + 1$ vertex-disjoint paths between $S$ and $T$ , or there is a set X…

math.CO2025

Asymptotic structure. III. Excluding a fat tree

Tung Nguyen, Alex Scott, Paul Seymour

Robertson and Seymour proved that for every finite tree $H$ , there exists $k$ such that every finite graph $G$ with no $H$ minor has path-width at most $k$ ; and conversely, for eve…

math.CO2025

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 $S, T$ are sets of vertices in a graph $G$ , then (for $k \geq 0$ ) either there are $k + 1$ vertex-disjoint paths between $S$ and $T$ , or there is a set…

math.CO2025

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…

math.CO2025

The vertex sets of subtrees of a tree

Maria Chudnovsky, Tung Nguyen, Alex Scott +1

Let $F$ be a set of subsets of a set $W$ . When is there a tree $T$ with vertex set $W$ such that each member of $F$ is the set of vertices of a subtree of $T$ ?…

math.CO2025

On polynomially high-chromatic pure pairs

Tung H. Nguyen

Let $T$ be a forest. We study polynomially high-chromatic pure pairs in graphs with no $T$ as an induced subgraph ( $T$ -free graphs in other words), with applications to the polynom…

math.CO2025

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 $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of…

math.CO2024

Distant digraph domination

Tung Nguyen, Alex Scott, Paul Seymour

A {\em $k$ -kernel} in a digraph $G$ is a stable set $X$ of vertices such that every vertex of $G$ can be joined from $X$ by a directed path of length at most $k$ . We prove three re…

math.CO2024

Subdivisions and near-linear stable sets

Tung Nguyen, Alex Scott, Paul Seymour

We prove that for every complete graph $K_{t}$ , all graphs $G$ with no induced subgraph isomorphic to a subdivision of $K_{t}$ have a stable subset of size at least $|G|/{\rm polylog}|…

math.CO2024★ 1 cited

Trees and near-linear stable sets

Tung Nguyen, Alex Scott, Paul Seymour

When $H$ is a forest, the Gyárfás-Sumner conjecture implies that every graph $G$ with no induced subgraph isomorphic to $H$ and with bounded clique number has a stable set of linea…

math.CO2024

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…

math.CO2024★ 1 cited

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 $k$ vertex-disjoint paths between two sets of vertices in a graph $G$ . Recently, Georgakopoulos and…

math.CO2023★ 3 cited

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 $d > 0$ , there exists $c > 0$ such that every $n$ -vertex graph of VC-dimension at most $d$ has a clique or stable set of s…

math.CO2023★ 3 cited

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 $P_{5}$ ; that is, there exists $c > 0$ such that every $n$ -vertex graph with no induced $P_{5}$ has a clique or stable set o…

math.CO2023

Induced subgraph density. V. All paths approach Erdos-Hajnal

Tung Nguyen, Alex Scott, Paul Seymour

The Erdős-Hajnal conjecture says that, for every graph $H$ , there exists $c > 0$ such that every $H$ -free graph on $n$ vertices has a clique or stable set of size at least $n^{c}$ . In…

math.CO2023★ 1 cited

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 $H$ , there exists $c > 0$ such that every $H$ -free graph $G$ has a clique or a stable set of size at least $∣ G ∣^{c}$ (a graph is $H$ -f…

math.CO2023★ 1 cited

Induced subgraph density. III. Cycles and subdivisions

Tung Nguyen, Alex Scott, Paul Seymour

We show that for every two cycles $C, D$ , there exists $c > 0$ such that if $G$ is both $C$ -free and $D$ -free then $G$ has a clique or stable set of size at least $∣ G ∣^{c}$ .…

math.CO2023★ 1 cited

Induced subgraph density. II. Sparse and dense sets in cographs

Jacob Fox, Tung Nguyen, Alex Scott +1

A well-known theorem of Rödl says that for every graph $H$ , and every $ε > 0$ , there exists $δ > 0$ such that if $G$ does not contain an induced copy of $H$ , then there exists $X\subse…

math.CO2023

Some results and problems on tournament structure

Tung Nguyen, Alex Scott, Paul Seymour

This paper is a survey of results and problems related to the following question: is it true that if G is a tournament with sufficiently large chromatic number, then G has two vert…

math.CO2023

On a problem of El-Zahar and Erdoos

Tung Nguyen, Alex Scott, Paul Seymour

Two subgraphs $A, B$ of a graph $G$ are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if $G$ is a graph with bounded clique number, a…

math.CO2023

Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Tung Nguyen, Alex Scott, Paul Seymour

We prove that for every path H, and every integer d, there is a polynomial f such that every graph G with chromatic number greater than f(t) either contains H as an induced subgrap…