[talks] Katherine Edwards will present her Pre-FPO on Tuesday, February 16, 2016 at 11am in CS 302.

[Nicki Gotsis]

Katherine Edwards will present her Pre-FPO on Tuesday, February 16, 2016 at 11am in CS 302.

The members of her committee are:  Paul Seymour (advisor), Maria Chudnovsky and Chun-Hung Liu; (readers - Math Dept) and Bernard Chazelle and Bob Tarjan (non-readers).

Everyone is invited to attend her talk.  The talk title and abstract follow below:

Title: A collection of results in graph theory

In this thesis, we present several results in graph theory. In this talk, we will highlight four of them.

First, we discuss two results about edge colouring. In 1966 Tutte conjectured that every two-connected cubic graph without the Petersen graph as a minor is three-edge colourable. This statement generalizes the celebrated four-colour theorem. In previous work, Seymour et al. showed that to prove Tutte’s conjecture, it is sufficient to prove it for apex graphs (graphs which can be made planar by deleting a vertex) and doublecross graphs (graphs which can be drawn in the plane with just two crossings, in the infinite region). Sanders and Thomas recently solved the apex case. With Sanders, Seymour and Thomas, we give a proof for the doublecross case.

Seymour conjectured in 1973 that every k-regular planar graph can be k-edge-coloured if and only if for every odd subset X of vertices, there are at least k edges between X and its complement. When k=3, this is the statement of the Four Colour theorem, and the conjecture had been proved for values of k up to 7. In joint work with Chudnovsky, Kawarabayashi and Seymour we give a proof for the case k=8 and a new, simpler proof for the case k=7.

Next, we will consider fractional vertex colourings of graphs not containing large cliques.
Fractional colouring is a generalization of graph colouring in which vertices are assigned sets of colours so that every pair of adjacent vertices receive disjoint sets. The fractional chromatic number is bounded above by the maximum degree \Delta, but in graphs which do not contain a clique of size Delta we can generally find stronger upper bounds. We will discuss some progress, joint with King, in bounding the fractional chromatic number of K_\Delta -free graphs away from \Delta. Our method relies on a local strengthening of the fractional relaxation of Reed's \omega, \Delta, \chi conjecture which roughly stipulates that if a graph has high fractional chromatic number then it must contain a vertex of high degree and a large clique in the same local area of the graph. We have also obtained new, stronger local bounds on the fractional chromatic number.

Finally, we discuss some work with applications in large graph analytics.
The hyperbolicity of a graph is an invariant which roughly measures the hyperbolicity of the metric space induced by its associated distance metric.
Many real-world networks have been shown experimentally to have a small hyperbolicity constant.
Such graphs also tend to be so large that superlinear-time algorithms are highly impractical, so it is interesting to design fast approximation algorithms for optimization problems on graphs with a fixed hyperbolicity. 
We investigate the $p$-centre problem, a popular clustering technique wherein we seek to locate $p$ centres on the graph for which the maximum distance from a vertex to its closest centre (this distance is called the $p$-radius $r_p$) is minimized.
With Kennedy and Saniee, we give a combinatorial linear-time approximation algorithm to determine $p$-centers with an additive error on $r_p$ of at most 3 times its hyperbolic constant.  This improves on the previously best-known quadratic time algorithm.