Backbone colouring: tree backbones with small diameter in planar graphs
type: Dataset
description: 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.
identifier: Report N°: RR-8151
issued: 2026-06-03T10:39:57.806717
language: en
modified: 2026-06-03T10:39:57.806723
contact point: Organization
  fn: CCSD
keyword: infoeu-reposemanticsreport
keyword: infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm
keyword: reports
landing page: https://inria.hal.science/hal-00758548

Backbone colouring: tree backbones with small diameter in planar graphs
type: Distribution
format: HTML
issued: 2026-06-03T10:39:57.819312
modified: 2026-06-03T10:39:57.795347
access URL: https://inria.hal.science/hal-00758548

test_moissonnage_selune
type: Agent