License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.85
URN: urn:nbn:de:0030-drops-64937
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6493/
Go to the corresponding LIPIcs Volume Portal

Kreutzer, Stephan ; Pilipczuk, Michal ; Rabinovich, Roman ; Siebertz, Sebastian

The Generalised Colouring Numbers on Classes of Bounded Expansion

pdf-format:
LIPIcs-MFCS-2016-85.pdf (0.5 MB)

Abstract

The generalised colouring numbers adm_r(G), col_r(G), and wcol_r(G) were introduced by Kierstead and Yang as generalisations of the usual colouring number, also known as the degeneracy of a graph, and have since then found important applications in the theory of bounded expansion and nowhere dense classes of graphs, introduced by Nesetril and Ossona de Mendez. In this paper, we study the relation of the colouring numbers with two other measures that characterise nowhere dense classes of graphs, namely with uniform quasi-wideness, studied first by Dawar et al. in the context of preservation theorems for first-order logic, and with the splitter game, introduced by Grohe et al. We show that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of r. Finally, we use our construction of such orders to give a new proof of a result of Eickmeyer and Kawarabayashi, showing that the model-checking problem for successor-invariant first-order formulas is fixed parameter tractable on classes of graphs with excluded topological minors.

BibTeX - Entry

@InProceedings{kreutzer_et_al:LIPIcs:2016:6493,
  author =	{Stephan Kreutzer and Michal Pilipczuk and Roman Rabinovich and Sebastian Siebertz},
  title =	{{The Generalised Colouring Numbers on Classes of Bounded Expansion}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{85:1--85:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6493},
  URN =		{urn:nbn:de:0030-drops-64937},
  doi =		{10.4230/LIPIcs.MFCS.2016.85},
  annote =	{Keywords: graph structure theory, nowhere dense graphs, generalised colouring numbers, splitter game, first-order model-checking}
}

Keywords: graph structure theory, nowhere dense graphs, generalised colouring numbers, splitter game, first-order model-checking
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI