Source author record

Jan van den Heuvel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Extensions of Fractional Precolorings show Discontinuous Behavior

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 at least d of a fractionally k-colorable graph can be extended to a fractional (k+epsilon)-coloring of the whole graph? The exact values of epsilon were known for k=2 and k\ge3 and any d. We determine the exact values of epsilon for k \in (2,3) if d=4, and k \in [2.5,3) if d=6, and give upper bounds for k \in (2,3) if d=5,7, and k \in (2,2.5) if d=6. Surprisingly, epsilon viewed as a function of k is discontinuous for all those values of d.

preprint2012arXiv

A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

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 vertices of $G$ such that, in addition, vertices that appear together in some $Σ(v)$ receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner's and Borodin's Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn's result that the list chromatic index is close to the fractional chromatic index. Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree $Δ$ embeddable in some fixed surface is at most $\frac32\,Δ$ plus a constant.

preprint2012arXiv

Fire Containment in Planar Graphs

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$ -surviving rate $ρ_k(G)$ of $G$ is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random. For a given class of graphs $\cG$ we are interested in the minimum value $k$ such that $ρ_k(G)\geε$ for some constant $ε>0$ and all $G\in\cG$ i.e., such that linearly many vertices are expected to be saved in every graph from $\cG$). In this note, we prove that for planar graphs this minimum value is at most 4, and that it is precisely 2 for triangle-free planar graphs.

preprint2011arXiv

Cyclic Orderings and Cyclic Arboricity of Matroids

We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid $M$ , weight function $ω:E(M)\rightarrow\mathbb{N}$ , and positive integer $D$ , the following are equivalent. (1) For all $A\subseteq E(M)$ , we have $\sum_{a\in A}ω(a)\le D\cdot r(A)$ . (2) There is a map $ϕ$ that assigns to each element $e$ of $E(M)$ a set $ϕ(e)$ of $ω(e)$ cyclically consecutive elements in the cycle $(1,2,...,D)$ so that each set $\{e|i\inϕ(e)\}$ , for $i=1,...,D$ , is independent. As a first corollary we obtain the following. For each matroid $M$ so that $|E(M)|$ and $r(M)$ are coprime, the following are equivalent. (1) For all non-empty $A\subseteq E(M)$ , we have $|A|/r(A)\le|E(M)|/r(M)$ . (2) There is a cyclic permutation of $E(M)$ in which all sets of $r(M)$ cyclically consecutive elements are bases of $M$ . A second corollary is that the circular arboricity of a matroid is equal to its fractional arboricity. These results generalise classical results of Edmonds, Nash-Williams and Tutte on covering and packing matroids by bases and graphs by spanning trees.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.