34 citations · 188 across the 74 of their papers we have counts for
11 papers · 1 filter
Induced subgraphs of graphs with large chromatic number. XII. Distant stars
Maria Chudnovsky, Alex Scott, Paul Seymour
The Gyarfas-Sumner conjecture asserts that if H is a tree then every graph with bounded clique number and very large chromatic number contains H as an induced subgraph. This is sti…
Induced subgraphs of graphs with large chromatic number. XI. Orientations
Maria Chudnovsky, Alex Scott, Paul Seymour
Fix an oriented graph H, and let G be a graph with bounded clique number and very large chromatic number. If we somehow orient its edges, must there be an induced subdigraph isomor…
Near-domination in graphs
Bruce Reed, Alex Scott, Paul Seymour
A vertex u of a graph t-dominates a vertex v if there are at most t vertices different from u,v that are adjacent to v and not to u; and a graph is t-dominating if for every pair o…
Clustered Colouring in Minor-Closed Classes
Sergey Norin, Alex Scott, Paul Seymour +1
The "clustered chromatic number" of a class of graphs is the minimum integer such that for some integer every graph in the class is -colourable with monochromatic compon…
Colouring perfect graphs with bounded clique number
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour +1
A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver from 1988 finds an…
Bad News for Chordal Partitions
Alex Scott, Paul Seymour, David R. Wood
Reed and Seymour [1998] asked whether every graph has a partition into induced connected non-empty bipartite subgraphs such that the quotient graph is chordal. If true, this would…