On problems related to graph colouring
Laura Gellert · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · 2017
In this thesis we study various problems from the prominent area of graph colourings. We provide a characterisation of t-perfect triangulations and quadrangulations of the projective plane. For the latter class, a novel method to transform quadrangulations of the sphere is developed. The involved operations are simple and minor-preserving, in contrast to other known methods. We conjecture that any graph with treewidth k and maximum degree ∆ ≥ k + √k has chromatic index ∆. In support of the conjecture we prove its fractional version by developing a new upper bound on the edge number of such graphs. We further prove the list colouring conjecture for generalised Petersen graphs of the form GP (3k,k) and GP (4k,k). In doing so, we discover an interesting connection between the number of 1-factorisations of GP (3k,k) and the Jacobsthal numbers. Finally, we develop new techniques to construct cycle decompositions. They work on the common neighbourhood of two degree-6 vertices. With these techniques we find structures that cannot occur in a minimal counterexample to Hajós’ conjecture and verify the conjecture for Eulerian graphs of pathwidth at most 6. This is the first time the conjecture has been verified for graphs that are not 4-degenerate.