Andrew D. King

activity

20092012

most citedExponentially many perfect matchings in cubic graphs

60 citations · 106 across the 13 of their papers we have counts for

collaborators

Showing 2012 · cs.DMShow all

4 papers · 2 filters

cs.DM2012

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 $χ \leq ⌈ \frac{1}{2} (Δ + 1 + ω)⌉$ . In this paper we prove that the conjecture holds for all cla…

cs.DM2012

A short proof that $χ$ can be bounded $ε$ away from $Δ + 1$ towards $ω$

Andrew D. King, Bruce A. Reed

In 1998 the second author proved that there is an $ε > 0$ such that every graph satisfies $χ \leq ⌈(1 - ε) (Δ + 1) + ε ω ⌉$ . The first author recently proved that any graph satisfyi…

cs.DM2012

A superlocal version of Reed's Conjecture

Katherine Edwards, Andrew D. King

Reed's well-known $ω$ , $Δ$ , $χ$ conjecture proposes that every graph satisfies $χ \leq ⌈ \frac{1}{2} (Δ + 1 + ω)⌉$ . The second author formulated a {\em local strengthening} of thi…

cs.DM2012

Bounding the fractional chromatic number of $K_{Δ}$ -free graphs

Katherine Edwards, Andrew D. King

King, Lu, and Peng recently proved that for $Δ \geq 4$ , any $K_{Δ}$ -free graph with maximum degree $Δ$ has fractional chromatic number at most $Δ - \frac{2}{67}$ unless it is isomorphi…

Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ

A short proof that χ can be bounded ε away from Δ+1 towards ω

A superlocal version of Reed's Conjecture

Bounding the fractional chromatic number of KΔ​-free graphs

Claw-free graphs, skeletal graphs, and a stronger conjecture on $ω$ , $Δ$ , and $χ$

A short proof that $χ$ can be bounded $ε$ away from $Δ + 1$ towards $ω$

Bounding the fractional chromatic number of $K_{Δ}$ -free graphs