Document Open Access Logo

The Generalised Colouring Numbers on Classes of Bounded Expansion

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

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.85.pdf
  • Filesize: 488 kB
  • 13 pages

Document Identifiers

Author Details

Stephan Kreutzer
Michal Pilipczuk
Roman Rabinovich
Sebastian Siebertz

Cite As Get BibTex

Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 85:1-85:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.85

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.

Subject Classification

Keywords
  • graph structure theory
  • nowhere dense graphs
  • generalised colouring numbers
  • splitter game
  • first-order model-checking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Albert Atserias, Anuj Dawar, and Phokion G Kolaitis. On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM (JACM), 53(2):208-237, 2006. Google Scholar
  2. Anuj Dawar. Homomorphism preservation on quasi-wide classes. Journal of Computer and System Sciences, 76(5):324-332, 2010. Google Scholar
  3. Reinhard Diestel. Graph Theory: Springer Graduate Text GTM 173, volume 173. Reinhard Diestel, 2012. Google Scholar
  4. Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse graphs. European Journal of Combinatorics, 34:833-840, 2013. Google Scholar
  5. Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM (JACM), 60(5):36, 2013. Google Scholar
  6. Kord Eickmeyer and K. Kawarabayashi. Personal communication, 2016. Google Scholar
  7. Kord Eickmeyer, K. Kawarabayashi, and Stephan Kreutzer. Model checking for successor-invariant first-order logic on minor-closed graph classes. In Proceedings of the 28th Annual IEEE/ACM Symposium on Logic in Computer Science (LICS), 2013, pages 134-142. IEEE, 2013. Google Scholar
  8. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 89-98. ACM, 2014. Google Scholar
  9. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM Journal on Computing, 44(1):114-159, 2015. Google Scholar
  10. Martin Grohe and Thomas Schwentick. Locality of order-invariant first-order formulas. ACM Transactions on Computational Logic (TOCL), 1(1):112-130, 2000. Google Scholar
  11. Hal A Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order, 20(3):255-264, 2003. Google Scholar
  12. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European Journal of Combinatorics, 29(3):760-776, 2008. Google Scholar
  13. Jaroslav Nešetřil and Patrice Ossona de Mendez. First order properties on nowhere dense structures. The Journal of Symbolic Logic, 75(03):868-887, 2010. Google Scholar
  14. Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600-617, 2011. Google Scholar
  15. Benjamin Rossman. Successor-invariant first-order logic on finite structures. The Journal of Symbolic Logic, 72(02):601-618, 2007. Google Scholar
  16. Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. CoRR, abs/1602.09052, 2016. URL: http://arxiv.org/abs/1602.09052.
  17. Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics, 309(18):5562-5568, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact