3 citations · 8 across the 14 of their papers we have counts for
5 papers · 1 filter
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…