34 citations · 188 across the 74 of their papers we have counts for
9 papers · 1 filter
Clique covers of H-free graphs
Tung Nguyen, Alex Scott, Paul Seymour +1
It takes cliques to cover all the edges of a complete bipartite graph , but how many cliques does it take to cover all the edges of a graph if has no $…
Dense minors of graphs with independence number two
Sergey Norin, Paul Seymour
Motivated by Hadwiger's conjecture, we prove that every -vertex graph with no independent set of size three contains an -vertex simple minor with $$0.9…
Bipartite graphs with no minor
Maria Chudnovsky, Alex Scott, Paul Seymour +1
A theorem of Mader shows that every graph with average degree at least eight has a minor, and this is false if we replace eight by any smaller constant. Replacing average deg…
Polynomial bounds for chromatic number VII. Disjoint holes
Maria Chudnovsky, Alex Scott, Paul Seymour +1
A hole in a graph is an induced cycle of length at least four, and a -multihole in is a set of pairwise disjoint and nonadjacent holes. It is well known that if does…
Pure pairs. X. Tournaments and the strong Erdos-Hajnal property
Maria Chudnovsky, Alex Scott, Paul Seymour +1
A pure pair in a tournament is an ordered pair of disjoint subsets of such that every vertex in is adjacent from every vertex in . Which tournaments h…
Polynomial bounds for chromatic number VI. Adding a four-vertex path
Maria Chudnovsky, Alex Scott, Paul Seymour +1
A class of graphs is -bounded if there is a function such that every graph in the class has chromatic number at most , where is the clique number of ;…