5 citations · 15 across the 13 of their papers we have counts for
6 papers · 1 filter
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…
Powers of paths and cycles in tournaments
António Girão, Dániel Korándi, Alex Scott
We show that for every positive integer , any tournament can be partitioned into at most -th powers of paths. This result is tight up to the exponential constant. Mo…
Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
Alex Scott, Paul Seymour, Sophie Spirkl
Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph as a subgraph, have bound…
Erdos-Hajnal for graphs with no 5-hole
Maria Chudnovsky, Alex Scott, Paul Seymour +1
The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality a…
Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
Alex Scott, Paul Seymour, Sophie Spirkl
For integer , let be the number of rows of the largest all-0 or all-1 square submatrix of , minimized over all -matrices . Thus …