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:

Reconfigurations of Combinatorial Problems: Graph Colouring and Hamiltonian Cycle

LIGNOS, IOANNIS (2017) Reconfigurations of Combinatorial Problems: Graph Colouring and Hamiltonian Cycle. Doctoral thesis, Durham University.

PDF - Accepted Version


We explore algorithmic aspects of two known combinatorial problems, Graph Colouring and Hamiltonian Cycle, by examining properties of their solution space. One can model the set of solutions of a combinatorial problem $P$ by the solution graph $R(P)$, where vertices are solutions of $P$ and there is an edge between two vertices, when the two corresponding solutions satisfy an adjacency reconfiguration rule. For example, we can define the reconfiguration rule for graph colouring to be that two solutions are adjacent when they differ in colour in exactly one vertex.

The exploration of the properties of the solution graph $R(P)$ can give rise to interesting questions. The connectivity of $R(P)$ is the most prominent question in this research area. This is reasonable, since the main motivation for modelling combinatorial solutions as a graph is to be able to transform one into the other in a stepwise fashion, by following paths between solutions in the graph. Connectivity questions can be made binary, that is expressed as decision problems which accept a 'yes' or 'no' answer. For example, given two specific solutions, is there a path between them? Is the graph of solutions $R(P)$ connected?

In this thesis, we first show that the diameter of the solution graph $R_{l}(G)$ of vertex $l$-colourings of k-colourable chordal and chordal bipartite graphs $G$ is $O(n^2)$, where $l > k$ and n is the number of vertices of $G$. Then, we formulate a decision problem on the connectivity of the graph colouring solution graph, where we allow extra colours to be used in order to enforce a path between two colourings with no path between them. We give some results for general instances and we also explore what kind of graphs pose a challenge to determine the complexity of the problem for general instances. Finally, we give a linear algorithm which decides whether there is a path between two solutions of the Hamiltonian Cycle Problem for graphs of maximum degree five, and thus providing insights towards the complexity classification of the decision problem.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Keywords:PhD, computer science, graph theory, reconfigurations, graph colouring, solution graph, hamiltonian cycle
Faculty and Department:Faculty of Science > Engineering and Computing Science, School of (2008-2017)
Thesis Date:2017
Copyright:Copyright of this thesis is held by the author
Deposited On:16 May 2017 13:46

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter