60 citations · 106 across the 13 of their papers we have counts for
5 papers · 1 filter
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 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…
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…
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…