Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We present an assortment of results in graph theory. First, Tutte conjectured that every two-edgeconnected

cubic graph with no Petersen graph minor is three-edge-colourable. This generalizes the

four-colour theorem. Robertson et al. had previously shown that to prove Tutte’s conjecture, it

was enough to prove it for doublecross graphs. We provide a proof of the doublecross case.

Seymour conjectured the following generalization of the four-colour theorem. Every d-regular

planar graph can be d-edge-coloured, provided that for every odd-cardinality set X of vertices,

there are at least d edges with exactly one end in X. Seymour’s conjecture was previously known

to be true for values of d ≤ 7. We provide a proof for the case d = 8.

We then discuss upper bounds for the fractional chromatic number of graphs not containing

large cliques. It has been conjectured that each graph with maximum degree at most ∆ and no

complete subgraph of size ∆ has fractional chromatic number bounded below ∆ by at least a

constant f(∆). We provide the currently best known bounds for f(∆), for 4 ≤ ∆ ≤ 103

. We also

give a general upper bound for the fractional chromatic number in terms of the sizes of cliques and

maximum degrees in local areas of a graph.

Next, we give a result that says, roughly, that a graph with sufficiently large treewidth contains

many disjoint subgraphs with ‘good’ linkedness properties. A similar result was a key tool in a

recent proof of a polynomial bound in the excluded grid theorem. Our theorem is a quantitative

improvement with a new proof.

Finally, we discuss the p-centre problem, a central NP-hard problem in graph clustering. Here

we are given a graph and an integer p, and need to identify a set of p vertices, called centres, so

that the maximum distance from a vertex to its closest centre (the p-radius) is minimized. We give

a quasilinear time approximation algorithm to solve p-centres when the hyperbolicity of the graph

is fixed, with a small additive error on the p-radius.