Tree-like distance colouring for planar graphs of sufficient girth

Ross J. Kang¹ ; Willem van Loon¹

¹Radboud University Nijmegen

The electronic journal of combinatorics, Tome 26 (2019) no. 1

Résumé

Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $\pi'_t(d)$ and $\tau'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$. We have that $\pi'_t(d)$ is at most and at least a non-trivial constant multiple larger than $\tau'_t(d)$. (We conjecture $\limsup_{d\to\infty}\pi'_2(d)/\tau'_2(d) =9/4$ in particular.) We prove for odd $t$ the existence of a quantity $g$ depending only on $t$ such that the distance-$t$ chromatic index of any planar multigraph of maximum degree $d$ and girth at least $g$ is at most $\tau'_t(d)$ if $d$ is sufficiently large. Such a quantity does not exist for even $t$. We also show a related, similar phenomenon for distance vertex-colouring.

Détail

DOI : 10.37236/8220

Classification : 05C15, 05C10, 05C35