Please use this identifier to cite or link to this item:

`http://arks.princeton.edu/ark:/88435/dsp01qj72p9619`

Title: | On edge colouring, fractionally colouring and partitioning graphs |

Authors: | Edwards, Katherine |

Advisors: | Seymour, Paul D |

Contributors: | Computer Science Department |

Keywords: | edge colouring fractional colouring graph colouring graph theory |

Subjects: | Mathematics Computer science |

Issue Date: | 2016 |

Publisher: | Princeton, NJ : Princeton University |

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 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. |

URI: | http://arks.princeton.edu/ark:/88435/dsp01qj72p9619 |

Alternate format: | The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu |

Type of Material: | Academic dissertations (Ph.D.) |

Language: | en |

Appears in Collections: | Computer Science |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

Edwards_princeton_0181D_11824.pdf | 1.28 MB | Adobe PDF | View/Download |

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.