34 citations · 188 across the 74 of their papers we have counts for
10 papers · 1 filter
Pure pairs. IX. Transversal trees
Alex Scott, Paul Seymour, Sophie Spirkl
Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this part…
Graphs with all holes the same length
Linda Cook, Jake Horsfield, Myriam Preissmann +5
A graph is "-holed" if all its induced cycles of length at least four have length exactly . We give a complete description of the -holed graphs for each $\ell\ge…
Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
Alex Scott, Paul Seymour, Sophie Spirkl
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a -free graph with clique number has chromatic number at most . The be…
Polynomial bounds for chromatic number. III. Excluding a double star
Alex Scott, Paul Seymour, Sophie Spirkl
A double star is a tree with two internal vertices. It is known that the Gyárfás-Sumner conjecture holds for double stars, that is, for every double star , there is a function $…
Polynomial bounds for chromatic number. II. Excluding a star-forest
Alex Scott, Paul Seymour, Sophie Spirkl
The Gyarfas-Sumner conjecture says that for every forest , there is a function such that if is -free then (where are the chromatic number and…
Strengthening Rodl's theorem
Maria Chudnovsky, Alex Scott, Paul Seymour +1
What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very d…