60 citations · 106 across the 13 of their papers we have counts for
6 papers · 1 filter
Optimal antithickenings of claw-free trigraphs
Maria Chudnovsky, Andrew D. King
Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: {\em compositions of strips} and {\…
A note on hitting maximum and maximal cliques with a stable set
Demetres Christofides, Katherine Edwards, Andrew D. King
It was recently proved that any graph satisfying contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satis…
A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs
Maria Chudnovsky, Andrew D. King, Matthieu Plumettaz +1
Reed's , , conjecture proposes that every graph satisfies ; it is known to hold for all claw-free graphs. In this paper we consider a l…
Finding a smallest odd hole in a claw-free graph using global structure
W. Sean Kennedy, Andrew D. King
A lemma of Fouquet implies that a claw-free graph contains an induced , contains no odd hole, or is quasi-line. In this paper we use this result to give an improved shortest-o…
A Fractional Analogue of Brooks' Theorem
Andrew D. King, Linyuan Lu, Xing Peng
Let be the maximum degree of a graph . Brooks' theorem states that the only connected graphs with chromatic number are complete graphs and odd cycles. We pr…
Asymptotics of the chromatic number for quasi-line graphs
Andrew D. King, Bruce Reed
As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically. That is, for any line graph we have . We…