J. van den Heuvel

activity

20082018

most citedImproper Colourings inspired by Hadwiger's Conjecture

47 citations · 124 across the 13 of their papers we have counts for

collaborators

Showing math.COShow all

12 papers · 1 filter

math.CO2017★ 47 cited

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…

math.CO2016★ 3 cited

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★ 8 cited

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…

math.CO2014

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…

math.CO2014★ 1 cited

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…

math.CO2012

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…

math.CO2011★ 20 cited

Fire Containment in Planar Graphs

Louis Esperet, Jan van den Heuvel, Frédéric Maffray +1

In a graph $G$ , a fire starts at some vertex. At every time step, firefighters can protect up to $k$ vertices, and then the fire spreads to all unprotected neighbours. The $k$ -surv…

math.CO2009

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 $M$ , weight function $ω : E (M) \to N$ , and positive integer $D$ , t…

math.CO2009★ 1 cited

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 $G$ to guarantee $G$ is $t$ -tough. We first give a best monotone theorem when $t \geq 1$ , but then show…

math.CO2009

Degree Sequences and the Existence of $k$ -Factors

D. Bauer, H. J. Broersma, J. van den Heuvel +2

We consider sufficient conditions for a degree sequence $π$ to be forcibly $k$ -factor graphical. We note that previous work on degrees and factors has focused primarily on finding…

math.CO2008★ 32 cited

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 $G$ : For given subsets $Σ (v)$ of neighbours of $v$ , for every $v \in V (G)$ , this is a proper colouring of the verti…

math.CO2008★ 7 cited

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 $G$ with maximum degree $Δ \geq 8$ is at most $⌊ \frac{3}{2} Δ ⌋ + 1$ . We show t…