On Treewidth and Graph Minors

Abstract

Both treewidth and the Hadwiger number are key graph parameters in structural and algorithmic graph theory, especially in the theory of graph minors. For example, treewidth demarcates the two major cases of the Robertson and Seymour proof of Wagner's Conjecture. Also, the Hadwiger number is the key measure of the structural complexity of a graph. In this thesis, we shall investigate these parameters on some interesting classes of graphs.

The treewidth of a graph defines, in some sense, how "tree-like" the graph is. Treewidth is a key parameter in the algorithmic field of fixed-parameter tractability. In particular, on classes of bounded treewidth, certain NP-Hard problems can be solved in polynomial time. In structural graph theory, treewidth is of key interest due to its part in the stronger form of Robertson and Seymour's Graph Minor Structure Theorem. A key fact is that the treewidth of a graph is tied to the size of its largest grid minor. In fact, treewidth is tied to a large number of other graph structural parameters, which this thesis thoroughly investigates. In doing so, some of the tying functions between these results are improved. This thesis also determines exactly the treewidth of the line graph of a complete graph. This is a critical example in a recent paper of Marx, and improves on a recent result by Grohe and Marx. By extending the techniques used, we also determine the treewidth of the line graph of a complete multipartite graph, up to lower order terms in general, and exactly whenever the complete multipartite graph is regular. This generalises a result by Lucena. We also determine a lower bound on the treewidth of any line graph; this result is similar to a question about the Hadwiger number of line graphs posed by Seymour, which was recently proven by DeVos et al.. Finally, we prove a result on the treewidth of the Kneser graph; in doing so we also prove a generalisation of the famous Erdős-Ko-Rado Theorem.

The Hadwiger number of a graph is the size of its largest complete minor. One of the most important conjectures in modern mathematics is Hadwiger's Conjecture, which conjectures that the Hadwiger number of a graph is at least its chromatic number. A related question is determining what lower bound on the average degree is required to ensure the existence of a K_t-minor (or, more generally, an H-minor for any graph H). The K_t-minor case has been thoroughly studied, and independently answered by Kostochka and Thomason. In this thesis we answer a slightly different question and present an algorithm for finding, in O(n) time, an H-minor forced by high average degree. Finally, this thesis determines a weakening of Hadwiger's Conjecture on the class of circular arc graphs, an interesting generalisation of the class of interval graphs, and in the process of doing so, proves some useful results about linkages in interval graphs.