Backbone colouring: tree backbones with small diameter in planar graphs

Given a graph $G$ and a spanning subgraph $T$ of $G$, a {\it backbone $k$-colouring} for $(G,T)$ is a mapping $c:V(G)\to{1,\ldots,k}$ such that $|c(u)-c(v)|\geq 2$ for every edge $uv\in E(T)$ and $|c(u)-c(v)|\geq 1$ for every edge $uv\in E(G)\setminus E(T)$. The {\it backbone chromatic number} $BBC(G,T)$ is the smallest integer $k$ such that there exists a backbone $k$-colouring of $(G,T)$. In 2007, Broersma et al. \cite{BFG+07} conjectured that $BBC(G,T)\leq 6$ for every planar graph $G$ and every spanning tree $T$ of $G$. In this paper, we prove this conjecture when $T$ has diameter at most four.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00758548
Author Campos, Victor, Havet, Frédéric, Sampaio, Rudini, Silva, Ana
Maintainer CCSD
Last Updated June 3, 2026, 10:39 (UTC)
Created June 3, 2026, 10:39 (UTC)
Identifier Report N°: RR-8151
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Parallelism, Graphs and Optimization Research Group (ParGO) ; Universidade Federal do Ceará = Federal University of Ceará (UFC)
creator Campos, Victor
date 2012-11-03T00:00:00
harvest_object_id f274c8ae-424b-46ab-b9b5-fff7fd5cacff
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-07T00:00:00
set_spec type:REPORT