J. van den Heuvel

activity

20162018

collaborators

5 papers

cs.LO2018

Model-Checking on Ordered Structures

Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…

math.CO2017

Improper Colourings inspired by Hadwiger's Conjecture

Jan van den Heuvel, David R. Wood

Hadwiger's Conjecture asserts that every $K_{t}$ -minor-free graph has a proper $(t - 1)$ -colouring. We relax the conclusion in Hadwiger's Conjecture via improper colourings. We prove t…

cs.LO2017

Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion

Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…

math.CO2016

Chromatic Numbers of Exact Distance Graphs

Jan van den Heuvel, H. A. Kierstead, Daniel A. Quiroz

For any graph $G = (V, E)$ and positive integer $p$ , the exact distance- $p$ graph $G^{[♮ p]}$ is the graph with vertex set $V$ , which has an edge between vertices $x$ and $y$ i…

math.CO2016

On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz +2

The generalised colouring numbers $col_{r} (G)$ and $wcol_{r} (G)$ were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…