Thesis icon

Thesis

Structure for algorithms, graph reconstruction and hypercube intersections

Alternative title:
Algorithms, reconstruction and hypercubes
Abstract:

We begin by studying several structural properties of graphs that lead to 'efficient' colouring algorithms. We first show that the treedepth of a Pt-free graph is bounded by t times its maximum degree, and use this to show that the number of 3-colourings can be computed in time O(2√tn log(n)) for any Pt-free graph on n vertices. We then prove that several graph classes, including the class of planar graphs, have asymptotic dimensi...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0002-9878-8750

Contributors

Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Sub department:
Mathematical Institute
Research group:
Combinatorics
Oxford college:
Merton College
Role:
Contributor, Supervisor
Role:
Examiner
Institution:
University of Cambridge
Role:
Examiner
More from this funder
Programme:
Clarendon-Merton Tira Wannamethee Scholarship
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP