34 citations · 188 across the 74 of their papers we have counts for
11 papers · 2 filters
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…
Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
Alex Scott, Paul Seymour
A large body of research in graph theory concerns the induced subgraphs of graphs with large chromatic number, and especially which induced cycles must occur. In this paper, we uni…
Induced subgraphs of graphs with large chromatic number. IX. Rainbow paths
Alex Scott, Paul Seymour
We prove that for all nonnegative integers k,s there exists c with the following property. Let G be a graph with clique number at most k and chromatic number more than c. Then for…
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
Maria Chudnovsky, Alex Scott, Paul Seymour +1
We prove a conjecture of Andras Gyarfas, that for all k,t, every graph with clique number at most k and sufficiently large chromatic number has an odd hole of length at least t.
Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
Alex Scott, Paul Seymour
A class of graphs is -bounded if there is a function such that for every induced subgraph of every graph in the class, where denote the chromatic…
Induced subgraphs of graphs with large chromatic number. VI. Banana trees
Alex Scott, Paul Seymour
We investigate which graphs H have the property that in every graph with bounded clique number and sufficiently large chromatic number, some induced subgraph is isomorphic to a sub…