60 citations · 106 across the 13 of their papers we have counts for
16 papers
Claw-free graphs, skeletal graphs, and a stronger conjecture on , , and
Andrew D. King, Bruce A. Reed
The second author's , , conjecture proposes that every graph satisties . In this paper we prove that the conjecture holds for all cla…
A short proof that can be bounded away from towards
Andrew D. King, Bruce A. Reed
In 1998 the second author proved that there is an such that every graph satisfies . The first author recently proved that any graph satisfyi…
Strongly even-cycle decomposable graphs
Tony Huynh, Andrew D. King, Sang-il Oum +1
A graph is strongly even-cycle decomposable if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several f…
A superlocal version of Reed's Conjecture
Katherine Edwards, Andrew D. King
Reed's well-known , , conjecture proposes that every graph satisfies . The second author formulated a {\em local strengthening} of thi…
Bounding the fractional chromatic number of -free graphs
Katherine Edwards, Andrew D. King
King, Lu, and Peng recently proved that for , any -free graph with maximum degree has fractional chromatic number at most unless it is isomorphi…
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…
Exponentially many perfect matchings in cubic graphs
Louis Esperet, Frantisek Kardos, Andrew King +2
We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. This version of the paper uses a…
A stronger result on fractional strong colourings
Andrew D. King
Aharoni, Berger and Ziv recently proved the fractional relaxation of the strong colouring conjecture. In this note we generalize their result as follows. Let and partitio…
Covering line graphs with equivalence relations
L. Esperet, J. Gimbel, A. King
An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph is the minimum number of equivalence subgraphs needed to cover the e…
Fractional total colourings of graphs of high girth
Tomas Kaiser, Andrew King, Daniel Kral
Reed conjectured that for every epsilon>0 and Delta there exists g such that the fractional total chromatic number of a graph with maximum degree Delta and girth at least g is at m…
Hitting all maximum cliques with a stable set using lopsided independent transversals
Andrew D. King
Rabern recently proved that any graph with omega >= (3/4)(Delta+1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exis…