47 citations · 124 across the 13 of their papers we have counts for
15 papers
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…
Improper Colourings inspired by Hadwiger's Conjecture
Jan van den Heuvel, David R. Wood
Hadwiger's Conjecture asserts that every -minor-free graph has a proper -colouring. We relax the conclusion in Hadwiger's Conjecture via improper colourings. We prove t…
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…
Chromatic Numbers of Exact Distance Graphs
Jan van den Heuvel, H. A. Kierstead, Daniel A. Quiroz
For any graph and positive integer , the exact distance- graph is the graph with vertex set , which has an edge between vertices and i…
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 and were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…
Extension from Precoloured Sets of Edges
Katherine Edwards, António Girão, Jan van den Heuvel +3
We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the c…
A Survey of Best Monotone Degree Conditions for Graph Properties
D. Bauer, H. J. Broersma, J. van den Heuvel +5
We survey sufficient degree conditions, for a variety of graph properties, that are best possible in the same sense that Chvatal's well-known degree condition for hamiltonicity is…
The Complexity of Change
Jan van den Heuvel
Many combinatorial problems can be formulated as "Can I transform configuration 1 into configuration 2, if certain transformations only are allowed?". An example of such a question…
Extensions of Fractional Precolorings show Discontinuous Behavior
Jan van den Heuvel, Daniel Kral, Martin Kupec +2
We study the following problem: given a real number k and integer d, what is the smallest epsilon such that any fractional (k+epsilon)-precoloring of vertices at pairwise distances…
Fire Containment in Planar Graphs
Louis Esperet, Jan van den Heuvel, Frédéric Maffray +1
In a graph , a fire starts at some vertex. At every time step, firefighters can protect up to vertices, and then the fire spreads to all unprotected neighbours. The -surv…
Cyclic Orderings and Cyclic Arboricity of Matroids
Jan van den Heuvel, Stéphan Thomassé
We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid , weight function , and positive integer , t…
Toughness and Vertex Degrees
D. Bauer, H. J. Broersma, J. van den Heuvel +2
We study theorems giving sufficient conditions on the vertex degrees of a graph to guarantee is -tough. We first give a best monotone theorem when , but then show…
Degree Sequences and the Existence of -Factors
D. Bauer, H. J. Broersma, J. van den Heuvel +2
We consider sufficient conditions for a degree sequence to be forcibly -factor graphical. We note that previous work on degrees and factors has focused primarily on finding…
A Unified Approach to Distance-Two Colouring of Graphs on Surfaces
Omid Amini, Louis Esperet, Jan van den Heuvel
In this paper we introduce the notion of -colouring of a graph : For given subsets of neighbours of , for every , this is a proper colouring of the verti…
List Colouring Squares of Planar Graphs
Frédéric Havet, Jan van den Heuvel, Colin McDiarmid +1
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph with maximum degree is at most . We show t…