| Summary: | <p>This thesis concerns the computational complexity of several combinatorial problems.</p><p>Chapter 1 is notation and definitions. In Chapter 2 the subgraph homeomorphism problem, for fixed pattern graphs H, is considered. For the cases H and#x2245; C<sub>6</sub>,C<sub>7</sub>,W<sub>4</sub> or W<sub>5</sub>, we obtain exact characterizations of graphs with no subgraph homeomorphic from H, and derive efficient algorithms for recognizing such graphs. We then consider counting homeomorphs, and show that if H is any finite nontrivial family of graphs then the problem of determining the number of subgraphs of a graph which are homeomorphic from a member of H is and#x2245; P-complete.</p><p>In Chapter 3 we consider languages in NP whose certificate size is bounded by a fixed, slowly growing function (say f(n)) of the input size. The classes f(n)-NP are defined in order to classify such languages; this is related to work of Kintala and Fischer. We show that several natural problems, involving Boolean satisfiability, graph colouring and Hamiltonian circuits are complete for f(n)-NP, and obtain in passing some new languages which are logspace complete for P.</p><p>Multicolouring is a natural generalization of graph colouring. We prove in Chapter 4 that determining whether a graph is (r,s)-colourable is NP-complete whenever s > 2r. This extends a result of Irving concerning the case s = 2r + 1. We also consider the complexity of some graph homomorphism problems.</p><p>In Chapter 5 we first give a polynomial time algorithm for 3-colouring graphs G whose minimum degree is > (8/ 15)|V(G)|. We then consider separability of disjoint pairs of languages, and obtain NP-hardness results for certain promise problems involving colouring.</p><p>The final Chapter concerns a problem of partitioning graphs subject to certain restrictions. We prove that several subproblems are NP-complete.</p>
|
|---|