[talks] Katherine Edwards will present her FPO, "On edge colouring, fractionally colouring and partitioning graphs" on Tuesday, 5/31/2016 at 11am in CS 402
ngotsis at CS.Princeton.EDU
Wed May 18 13:25:16 EDT 2016
Katherine Edwards will present her FPO "On edge colouring, fractionally colouring and partitioning graphs" on Tuesday, 5/31/2016 at 11am, 402 Computer Science Building.
The members of her committee are Paul Seymour (adviser), Readers: Maria Chudnovsky (Math) and Chun-Hung Liu (Math); Nonreaders: Robert Tarjan and Bernard Chazelle.
A copy of her thesis is available in Room 310.
Everyone is invited to attend her talk. The abstract follow below.
We present an assortment of results in graph theory. First, Tutte conjectured that every two-edge connected
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 double cross 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 su"ciently 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.
More information about the talks