On graph sparsity and structure : colourings and graph decompositions

Stavropoulos, Konstantinos; Grohe, Martin (Thesis advisor); Chepoi, Victor (Thesis advisor)

Aachen (2016)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2016

Abstract

We study structural aspects both of sparse and dense graph classes. In particular, we study in detail generalised colourings for sparse classes and their combinatorial applications to other related notions. Furthermore, we extend the known concept of tree decompositions which is central in the theory of Graph Minors and various other classes of sparse graphs, now as a structural tool for classifying dense graph classes. Bounded expansion and nowhere dense classes of graphs are relatively new families of graph classes generalising many commonly studied sparse graph classes such as classes of graphs of bounded degree and classes defined by excluded (topological) minors. They can be characterised through the generalised colouring numbers, for which we show various lower and upper bounds. We utilise the generalised colouring numbers to prove colouring results related to distance colourings of graphs and to obtain a new characterisation of bounded expansion by the notion of neighbourhood complexity. We generalise tree decompositions by introducing median decompositions along with their respective medianwidth invariants, where a graph can be modelled after any median graph. Depending on the notion of dimension we consider, this gives rise to hierachies of graph parameters that start from treewidth or pathwidth and converge to the clique number. Another variation of the parameter characterises the chromatic number of a graph. We provide characterisations of the parameters via intersections of tree or path decompositions and by a generalisation of the classical Cops and Robber game, where the robber plays against not just one team of cops, but many teams of cops simultaneously. Contrary to tree decompositions, we demonstrate that the high-dimensional nature of general median decompositions and their medianwidth parameters makes them more suitable for the study of classes of dense graphs.