### Contact

andrew.d.king@gmail.com

### Coauthors

(URLs may be outdated or nonexistent)

## Andrew D. King

My name is Andrew King, and I am an optimization algorithms analyst at D-Wave Systems. I perviously studied graph theory at Simon Fraser University with Pavol Hell, Bojan Mohar and others. I did my Ph.D. at McGill University with Bruce Reed, and recently spent time working at Columbia University with Maria Chudnovsky and at Charles University in Prague with Daniel Kral.

### Preprints

 A short proof that χ can be bounded ε away from Δ + 1 towards ω Andrew D. King and Bruce A. Reed arXiv preprint 1211.1410, 2012. In 1998 the second author proved that there is an \$ε>0\$ such that every graph satisfies \$χ ≤ ⌈ (1-ε)(Δ+1)+εω⌉\$. The first author recently proved that any graph satisfying \$ω > (2/3)(Δ+1)\$ contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Hall's Theorem, Brooks' Theorem, the Lov\'asz Local Lemma, and Talagrand's Inequality. [arXiv] List circular backbone colouring Frédéric Havet and Andrew D. King Submitted. INRIA preprint 00759527, 2012. A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the \$q\$-backbone colouring problem, these minimum distances are either \$q\$ or \$1\$, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in \$\Z_p\$ -- this problem is closely related to the problem of circular choosability. We first prove that the list circular \$q\$-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs. [preprint] Strongly even cycle decomposable graphs Tony Huynh, Andrew D. King, Sang-Il Oum, and Maryam Verdian-Rizi Submitted. arXiv preprint 1209.0160, 2012. We introduce the notion of an Eulerian graph being strongly even cycle decomposable, and note that a few basic classes have this property. We then prove that several fundamental composition operations that preserve the property of being Eulerian also preserve the property of being strongly even cycle decomposable. Our composition operations imply that all simple Eulerian k-partite graphs are strongly even cycle decomposable, with the exception of K_5. [arXiv] A superlocal version of Reed's Conjecture Katherine Edwards and Andrew D. King Submitted. arXiv preprint 1208.5188, 2012. Reed's well-known ω, Δ, χ conjecture proposes that every graph satisfies \$χ ≤ ⌈ (1/2)(Δ+1+ω)⌉\$. The second author formulated a local strengthening of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further. [arXiv] Optimal antithickenings of claw-free trigraphs Maria Chudnovsky and Andrew D. King Submitted. arXiv preprint 1110.5111, 2011. Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: compositions of strips and thickenings In this paper we consider the latter, proving that every claw-free graph has a unique optimal antithickening, where our definition of optimal is chosen carefully to respect the structural foundation of the graph. Furthermore, we give an algorithm to find the optimal antithickening in \$O(m^2)\$ time. For the sake of both completeness and ease of proof, we prove stronger results in the more general setting of trigraphs. [arXiv]

### Published and Accepted Articles

 Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ Andrew D. King and Bruce A. Reed Journal of Graph Theory, accepted, 2014. The second author's ω, Δ, χ conjecture proposes that every graph satisties χ ≤ ⌈(1/2)(Δ+1+ω)⌉. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful χ-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs. [arXiv] (Circular) backbone colouring: tree backbones in planar graphs Frédéric Havet, Andrew D. King, Mathieu Liedloff and Ioan Todinca Discrete Applied Mathematics, accepted, 2013. Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem. [preprint] Finding a smallest odd hole in a claw-free graph using global structure Andrew D. King and W. Sean Kennedy Discrete Applied Mathematics, 161, 2492–2498, 2013. A lemma of Fouquet implies that a claw-free graph contains an induced \$C_5\$, contains no odd hole, or is quasi-line. In this paper we use this result to give an improved shortest-odd-hole algorithm for claw-free graphs by exploiting the structural relationship between line graphs and quasi-line graphs suggested by Chudnovsky and Seymour's structure theorem for quasi-line graphs. Our approach involves reducing the problem to that of finding a shortest odd cycle of length \$≥ 5\$ in a graph. Our algorithm runs in \$O(m^2+n^2\log n)\$ time, improving upon Shrem, Stern, and Golumbic's recent \$O(nm^2)\$ algorithm, which uses a local approach. The best known recognition algorithms for claw-free graphs run in \$O(m^{1.69}) ∩ O(n^{3.5})\$ time, or \$O(m^2) ∩ O(n^{3.5})\$ without fast matrix multiplication. [arXiv] [doi] Bounding the fractional chromatic number of KΔ-free graphs Katherine Edwards and Andrew D. King SIAM J. Discrete Math., 27, 1184–1208, 2013. King, Lu, and Peng recently proved that for \$Δ≥ 4\$, any \$K_Δ\$-free graph with maximum degree Δ has fractional chromatic number at most \$Δ-(2/67)\$ unless it is isomorphic to \$C_5\boxtimes K_2\$ or \$C_8^2\$. Using a different approach we give improved bounds for \$Δ≥ 6\$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's ω, Δ, χ conjecture. [arXiv] [doi] A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs Maria Chudnovsky, Andrew D. King, Matthieu Plumettaz, and Paul Seymour SIAM J. Discrete Math., 27, 95–108, 2013. Reed's ω, Δ, χ conjecture proposes that every graph satisfies \$χ≤ ⌈(1/2)(Δ+1+ω)⌉\$; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colourings that achieve our bounds: \$O(n^2)\$ for line graphs and \$O(n^3m^2)\$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a colouring that achieves the bound of Reed's original conjecture. [arXiv] [doi] A note on hitting maximum and maximal cliques with a stable set Demetres Christofides, Katherine Edwards, and Andrew D. King Journal of Graph Theory, 73: 354–360, 2013. It was recently proved that any graph satisfying \$ω > (2/3)(Δ+1)\$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying \$ω ≥ (2/3)(Δ+1)\$ unless the graph is the strong product of \$K_{ω/2}\$ and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique. [arXiv] [doi] Asymptotics of the chromatic number for quasi-line graphs Andrew D. King and Bruce Reed Journal of Graph Theory, 73: 327–341, 2013. As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically. That is, for any line graph \$G\$ we have \$χ(G) ≤ (1+o(1))χ_f(G)\$. We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore we prove that we can construct a colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs. [arXiv] [doi] A fractional analogue of Brooks' Theorem Andrew D. King, Linyuan Lu and Xing Peng SIAM J. Discrete Math., 26, 452–471, 2012. Let \$Δ(G)\$ be the maximum degree of a graph \$G\$. Brooks' theorem states that the only connected graphs with chromatic number \$χ(G)=Δ(G)+1\$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs \$G\$ such that the fractional chromatic number \$χ_f(G)\$ is at least \$Δ(G)\$. These graphs are complete graphs, odd cycles, \$C^2_8\$, \$C_5\boxtimes K_2\$, and graphs whose clique number \$ω(G)\$ equals the maximum degree \$Δ(G)\$. Among the two sporadic graphs, the graph \$C^2_8\$ is the square graph of cycle \$C_8\$ while the other graph \$C_5\boxtimes K_2\$ is the strong product of \$C_5\$ and \$K_2\$. In fact, we prove a stronger result; if a connected graph \$G\$ with \$Δ(G)≥ 4\$ is not one of the graphs listed above, then we have \$χ_f(G)≤ Δ(G)- 2/67\$. [arXiv] [doi] Exponentially many perfect matchings in cubic graphs Louis Esperet, František Kardoš, Andrew D. King, Daniel Král', and Serguei Norine Advances in Mathematics, 227: 1646–1664, 2011. 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. The arXiv version of the paper uses a different definition of a burl from the journal version of the paper and a different proof of Lemma 18 is given. This simplifies the exposition of our arguments throughout the whole paper. [arXiv] [doi] Hitting all maximum cliques with a stable set using lopsided independent transversals Andrew D. King Journal of Graph Theory, 67: 300–305, 2011. Rabern recently proved that any graph with ω ≥ (3/4)(Δ+1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with omega > (2/3)(Δ+1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size. [arXiv] [doi] Fractional total colourings of graphs of high girth Tomáš Kaiser, Andrew King, and Daniel Král' Journal of Combinatorial Theory, Series B, 101: 383–402, 2011. Reed conjectured that for every ε>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+ε. We prove the conjecture for Δ=3 and for even Δ≥4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1. [arXiv] [doi] Covering line graphs with equivalence relations Louis Esperet, John Gimbel, and Andrew King Discrete Applied Mathematics, 158: 1902–1907, 2010. An equivalence graph is a disjoint union of cliques, and the equivalence number \$eq(G)\$ of a graph \$G\$ is the minimum number of equivalence subgraphs needed to cover the edges of \$G\$. We consider the case in which \$G\$ is a line graph, giving improved upper and lower bounds: \$(1/3) \log_2\log_2 χ(G) ≤ eq(L(G)) ≤ 2\log_2\log_2 χ(G) + 2\$. This disproves a recent conjecture that \$eq(L(G))\$ is at most three for triangle-free \$G\$; indeed it can be arbitrarily large. To bound \$eq(L(G))\$ we bound the closely-related invariant \$σ(G)\$, which is the minimum number of orientations of \$G\$ such that for two incident edges \$e,f\$ incident to \$v\$, both \$e\$ and \$f\$ are oriented out of \$v\$ in some orientation. When \$G\$ is triangle-free, \$σ(G)=eq(L(G))\$, and we prove that even in this case it is NP-hard to decide whether or not \$σ(G)≤ 3\$. [PDF] [doi] Finding the maximum-weight induced k-partite subgraph of an i-triangulated graph Louigi Addario-Berry, William (Sean) Kennedy, Andrew King, Zhentao Li, and Bruce Reed Discrete Applied Mathematics, 158: 765–770, 2010. An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete. [PS] [doi] The firefighter problem for cubic graphs Andrew King and Gary MacGillivray Discrete Mathematics, 310: 614–621, 2010. We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two. [PDF] [doi] Bounding χ in terms of ω and Δ for quasi-line graphs Andrew King and Bruce Reed Journal of Graph Theory, 59: 215–228, 2008. A quasi-line graph is a graph in which the neighbourhood of any vertex can be covered by two cliques; every line graph is a quasi-line graph. Reed conjectured that for any graph \$G\$, \$χ(G) ≤ ⌈ (1/2)(Δ(G)+1+ω(G))⌉\$. We prove that the conjecture holds if \$G\$ is a quasi-line graph, extending a result of King, Reed and Vetta, who proved the conjecture for line graphs, and improving the bound of \$χ(G) ≤ (3/2)ω(G)\$ given by Chudnovsky and Ovetsky. [PDF] [doi] An upper bound for the chromatic number of line graphs Andrew King, Bruce Reed, and Adrian Vetta European Journal of Combinatorics, 28: 2182–2187, 2007. It was conjectured by Reed that for any graph \$G\$, the graph's chromatic number \$χ(G)\$ is bounded above by \$⌈(1/2)(Δ(G) +1 + ω(G))⌉\$, where \$Δ(G)\$ and \$ω(G)\$ are the maximum degree and clique number of \$G\$, respectively. In this paper we prove that this bound holds if \$G\$ is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph \$G\$ and produces a colouring that achieves our bound. [PS] [doi] The firefighter problem for graphs of maximum degree three Stephen Finbow, Andrew King, Gary MacGillivray, and Romeo Rizzi Discrete Mathematics, 307: 2094–2105, 2007. We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two. [PS] [PDF] [doi] Generating indecomposable permutations Andrew King Discrete Mathematics, 306: 508–518, 2006. An indecomposable permutation π on [n] is one such that π([m])=[m] for no m

### Theses, Book Chapters, and Reports

 Protein Complex Prediction with RNSC Igor Jurisica, Andrew King, and Nataša Pržulj Chapter 16 in Denis Thieffry et al. (eds.), Bacterial Molecular Networks: Methods and Protocols, Methods in Molecular Biology, 804. DOI 10.1007/978-1-61779-361-5_16 [doi] Claw-free graphs and two conjectures on ω, Δ, and χ Andrew King Ph.D. thesis, McGill University. Compact version: 138 pages. [PDF] An Efficient Cost-Based Graph Clustering Algorithm Andrew King Technical report, University of Toronto. This report describes a much-improved version of the RNSC algorithm presented in the thesis. [PS] Graph clustering with Restricted Neighbourhood Search Andrew King M.Sc. thesis, Dept. of Computer Science, University of Toronto, 2004. [PS]