On graph sparsity and structure : colourings and graph decompositions

Stavropoulos, Konstantinos; Chepoi, Victor; Grohe, Martin

doi:HT019445092

On graph sparsity and structure : colourings and graph decompositions

Stavropoulos, Konstantinos

2016

Verantwortlichkeitsangabevorgelegt von Konstantionos Stavropoulos, M.Sc.

ImpressumAachen 2016

Umfang1 Online-Ressource (121 Seiten) : Diagramme

Dissertation, RWTH Aachen University, 2016

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Chepoi, Victor (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2016-11-21

Online
DOI: 10.18154/RWTH-2017-08007
URL: http://publications.rwth-aachen.de/record/699002/files/699002.pdf
URL: http://publications.rwth-aachen.de/record/699002/files/699002.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
bounded expansion (frei) ; generalised colouring numbers (frei) ; graph decompositions (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Wir untersuchen strukturelle Aspekte von Klassen magerer und dichter Graphen. Insbesondere betrachten wir verallgemeinerte Färbungen für magere Klassen und deren kombinatorische Anwendungen. Ausserdem erweitern wir das bekannte Konzept der Baumzerlegungen und erhalten auf diese Weise ein strukturelles Werkzeug zur Klassifikation dichter Graphklassen. Graphklassen mit beschränkter Expansion und nirgends dichte Graphklassen sind relativ neue Familien von Klassen, die viele bekannte magere Graphklassen verallgemeinern, wie etwa Klassen von Graphen mit beschränktem Grad und Klassen mit verbotenen (topologischen) Minoren. Sie können mit Hilfe der verallgemeinerten Färbungszahlen charakterisiert werden, für die wir untere und obere Schranken zeigen. Wir verwenden die verallgemeinerten Färbungszahlen, um Färbungsresultate mit Bezug zu Abstandsfärbungen von Graphen zu beweisen und um eine neue Charakterisierung von beschränkter Expansion mittels des Konzepts der Nachbarschaftskomplexität zu erhalten. Wir verallgemeinern Baumzerlegungen, indem wir Medianzerlegungen sowie entsprechende Medianweiten-Invarianten einführen. Bei solchen Zerlegungen wird ein Graph nach einem beliebigen Mediangraphen modelliert. In Abhängigkeit vom betrachteten Dimensionsbegriff ergeben sich dadurch Hierarchien von Graphparametern, die bei Baumweite oder Wegweite beginnen und gegen die Cliquenzahl konvergieren. Eine andere Parametervariante wiederum charakterisiert die chromatische Zahl eines Graphen. Wir geben Charakterisierungen der Parameter durch Schnitte von Baum- bzw. Wegzerlegungen und durch eine Verallgemeinerung des klassischen Räuber-und-Polizisten-Spiels, in dem der Räuber nicht gegen nur ein einziges, sondern gleichzeitig gegen mehrere Teams von Polizisten antritt. Wir zeigen auf, dass allgemeine Medianzerlegungen und die entsprechenden Medianweiten-Parameter, anders als Baumzerlegungen, aufgrund ihrer Hochdimensionalität besser zur Untersuchung von Klassen dichter Graphen geeignet sind.

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.

OpenAccess:
PDF PDF (PDFA)
(additional files)