[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
Nicki Gotsis
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.
Abstract:
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
mailing list