We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

Graph Partitioning With Input Restrictions

SMITH, SIANI,ALICE (2022) Graph Partitioning With Input Restrictions. Doctoral thesis, Durham University.

PDF - Accepted Version


In this thesis we study the computational complexity of a number of graph
partitioning problems under a variety of input restrictions. Predominantly,
we research problems related to Colouring in the case where the input
is limited to hereditary graph classes, graphs of bounded diameter or some
combination of the two.
In Chapter 2 we demonstrate the dramatic eect that restricting our
input to hereditary graph classes can have on the complexity of a decision
problem. To do this, we show extreme jumps in the complexity of three
problems related to graph colouring between the class of all graphs and every
other hereditary graph class.
We then consider the problems Colouring and k-Colouring for Hfree graphs of bounded diameter in Chapter 3. A graph class is said to be
H-free for some graph H if it contains no induced subgraph isomorphic to
H. Similarly, G is said to be H-free for some set of graphs H, if it does not
contain any graph in H as an induced subgraph. Here, the set H consists
usually of a single cycle or tree but may also contain a number of cycles, for
example we give results for graphs of bounded diameter and girth.
Chapter 4 is dedicated to three variants of the Colouring problem,
Acyclic Colouring, Star Colouring, and Injective Colouring.
We give complete or almost complete dichotomies for each of these decision
problems restricted to H-free graphs.
In Chapter 5 we study these problems, along with three further variants of
3-Colouring, Independent Odd Cycle Transversal, Independent
Feedback Vertex Set and Near-Bipartiteness, for H-free graphs of
bounded diameter.
Finally, Chapter 6 deals with a dierent variety of problems. We study
the problems Disjoint Paths and Disjoint Connected Subgraphs for
H-free graphs.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Faculty and Department:Faculty of Science > Computer Science, Department of
Thesis Date:2022
Copyright:Copyright of this thesis is held by the author
Deposited On:31 May 2022 11:09

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter