# Backbone colouring of chordal graphs

Júlio Araújo, Nicolas Nisse, Lucas Picasarri-Arrieta

► To cite this version:

Júlio Araújo, Nicolas Nisse, Lucas Picasarri-Arrieta. Backbone colouring of chordal graphs. XIII Latin American Algorithms, Graphs, and Optimization Symposium – LAGOS 2025, Nov 2025, Buenos Aires, Argentina. pp.133-140, 10.1016/j.procs.2025.10.290. hal-05285899

HAL Id: hal-05285899

https://hal.science/hal-05285899v1

Submitted on 26 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Backbone colouring of chordal graphs*

Júlio Araújo¹, Nicolas Nisse², and Lucas Picasarri-Arrieta³

¹Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

²Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France

³National Institute of Informatics, Tokyo, Japan

## Abstract

A proper *k*-colouring of a graph $G = (V, E)$ is a function $c : V(G) \to \{1, \dots, k\}$ such that $c(u) \neq c(v)$ for every edge $uv \in E(G)$. The chromatic number $\chi(G)$ is the minimum $k$ such that there exists a proper *k*-colouring of $G$. Given a spanning subgraph $H$ of $G$, a *q*-backbone *k*-colouring of $(G, H)$ is a proper *k*-colouring $c$ of $G$ such that $|c(u) - c(v)| \geq q$ for every edge $uv \in E(H)$. The *q*-backbone chromatic number $BBC_q(G, H)$ is the smallest $k$ for which there exists a *q*-backbone *k*-colouring of $(G, H)$. In their seminal paper, Broersma et al. [11] ask whether, for any chordal graph $G$ and any spanning forest $H$ of $G$, we have that $BBC_2(G, H) \leq \chi(G) + O(1)$.

In this work, we first show that this is true as long as $H$ is bipartite and $G$ is an interval graph in which each vertex belongs to at most two maximal cliques. We then show that this does not extend to bipartite graphs as backbone by exhibiting a family of chordal graphs $G$ with spanning bipartite subgraphs $H$ satisfying $BBC_2(G, H) \geq \frac{5\chi(G)}{3}$. Then, we show that if $G$ is chordal and $H$ has bounded maximum average degree (in particular, if $H$ is a forest), then $BBC_2(G, H) \leq \chi(G) + O(\sqrt{\chi(G)})$. We finally show that $BBC_2(G, H) \leq \frac{3}{2}\chi(G) + O(1)$ holds whenever $G$ is chordal and $H$ is $C_4$-free.

**Keywords:** Graph colouring, Chordal graph, Backbone colouring, Tree-decomposition, Maximum average degree.

## 1 Introduction

Let $G = (V, E)$ be a graph. Given a positive integer $k$, we denote the set $\{n \in \mathbb{N} | 1 \leq n \leq k\}$ by $[k]$. A proper *k*-colouring of $G$ is a function $c : V(G) \to [k]$ such that $c(u) \neq c(v)$ holds

<footnote>*This work has been founded by JST as part of ASPIRE, Grant Number JPMJAP2302, by CNPq (Brazil) projects 313153/2021-3 and 404613/2023-3, by Inria Associated Team CANOE and project CAPES-Cofecub 49587PE (Brazil-France) and ANR-17-EURE-0004 "EUR DS4H Investments in the Future".</footnote>
for every edge $uv \in E(G)$. We say $G$ is $k$-colourable if there exists a proper $k$-colouring of $G$. The chromatic number of $G$, denoted by $\chi(G)$, is the smallest $k$ for which $G$ is $k$-colourable. We say $G$ is $k$-chromatic if $\chi(G) = k$. The VERTEX COLOURING PROBLEM consists of determining $\chi(G)$, for a given graph $G$. It is a well-known NP-hard problem [18] and one of the most studied problems on Graph Theory [17, 19].

The VERTEX COLOURING PROBLEM models several practical applications, frequency assignment problems being perhaps the most famous ones [1]. There are several variations of the VERTEX COLOURING PROBLEM that were defined in order to model the specific constraints of the practical applications related to frequency assignment in networks. Broersma et al. [11, 10] defined the BACKBONE COLOURING PROBLEM to model the situation where certain channels of communication are more demanding than others.

Formally, given a graph $G$, a spanning subgraph $H$ of $G$, called the *backbone* of $G$, and two positive integers $q$ and $k$, a $q$-backbone $k$-colouring of $(G, H)$ is a proper $k$-colouring $c$ of $G$ for which $|c(u) - c(v)| \ge q$ holds for every $uv \in E(H)$. The $q$-backbone chromatic number of $(G, H)$, denoted by $BBC_q(G, H)$, is the minimum $k$ for which there exists a $q$-backbone $k$-colouring of $(G, H)$. The BACKBONE COLOURING PROBLEM consists of determining $BBC_q(G, H)$ [11, 10].

Observe that, if $H$ is edgeless, then $BBC_q(G, H) = \chi(G)$; hence computing $BBC_q(G, H)$ is an NP-hard problem. It has also been proved that the same holds even if $G$ belongs to particular graph classes such as planar graphs and $H$ is a Hamiltonian path or a matching of $G$ [16].

Note that if $f$ is a proper $k$-colouring of $G$, then the function $g: V \to [q \cdot k - q + 1]$ defined by $g(v) = q \cdot f(v) - q + 1$ is a $q$-backbone colouring of $(G, H)$, for any spanning subgraph $H$ of $G$. Moreover it is well-known that if $G = H$ and $f$ is a proper $\chi(G)$-colouring of $G$, this $q$-backbone colouring $g$ of $(G, H)$ is optimal. Therefore, since $BBC_q(H, H) \le BBC_q(G, H)$ and $BBC_q(G, H) \le BBC_q(G, G)$, we have

$$q \cdot \chi(H) - q + 1 \le BBC_q(G, H) \le q \cdot \chi(G) - q + 1. \quad (1)$$

In this work, we give a collection of results on the $q$-backbone chromatic number of a given pair $(G, H)$. However, in order to present results in the literature, let us briefly mention other variants of Backbone Colourings that are found in the literature.

**Related work.** A natural and well-studied variant is the one that imposes a circular metric on the colours. We can see $\mathbb{Z}_k^1$ as a cycle of length $k$ with vertex set $\{1, \dots, k\}$ together with the graphical distance $| \cdot |_k$. Then $|a - b|_k \ge q$ if and only if $q \le |a - b| \le k - q$. A circular $q$-backbone $k$-colouring of $(G, H)$ is a mapping $f: V(G) \to \mathbb{Z}_k$ such that $c(v) \ne c(u)$, for each edge $uv \in E(G)$, and $q \le |c(u) - c(v)| \le k - q$ for each edge $uv \in E(H)$. The circular $q$-backbone chromatic number of a graph pair $(G, H)$, denoted $CBC_q(G, H)$, is the minimum $k$ such that $(G, H)$ admits a circular $q$-backbone $k$-colouring.

Note that if $f$ is a circular $q$-backbone $k$-colouring of $(G, H)$, then $f$ is also a $q$-backbone $k$-colouring of $(G, H)$. On the other hand, observe that a $q$-backbone $k$-colouring $f$ of $(G, H)$

<footnote n="1">¹Whenever we refer to $\mathbb{Z}_k$, we mean the group of integers modulo $k$, also denoted by $\mathbb{Z}/k\mathbb{Z}$.</footnote>
is a circular q-backbone (k + q − 1)-colouring of ( G, H ). Hence for every graph pair ( G, H ), where H is a spanning subgraph of G , we have

$$
\mathrm{BBC}_{q}(G, H) \leq \mathrm{CBC}_{q}(G, H) \leq \mathrm{BBC}_{q}(G, H) + q - 1. \qquad (2)
$$

Combining Inequalities (1) and (2), we observe that

$$
q \cdot \chi(H) - q + 1 \leq \mathrm{CBC}_q(G, H) \leq q \cdot \chi(G). \qquad (3)
$$

One can also find a list variant of Backbone Colourings [15] in the literature and, more recently, Araujo et al. [6] introduced a variant for oriented backbones.

Let us consider the upper bound provided by (1) when q = 2. If G is planar, by the Four Colour Theorem [2, 3] we have that BBC$_{2}$( G, H ) ≤ 7. If G is a chordal graph, since it is perfect, we know that BBC$_{2}$( G, H ) ≤ 2 χ ( G ) − 1 = 2 ω ( G ) − 1. In their seminal work, Broersma et al. [11] raised two questions that, to the best of our knowledge, are still open.

**Problem 1 ([11]).** If G is planar and H is a spanning forest of G , then is it true that BBC$_{2}$( G, H ) ≤ 6?

**Problem 2 ([11]).** Does there exist a positive integer c such that, for any chordal graph G and any spanning forest H of G , we have that BBC$_{2}$( G, H ) ≤ ω ( G ) + c ?

Concerning Problem 1, the authors also asked for a proof that BBC$_{2}$( G, H ) ≤ 7, given a planar graph G and a spanning forest H of G , without using the Four Colour Theorem. Many authors in the literature considered that the answer to Problem 1 should be affirmative and it is treated as a conjecture by most of the related works. This conjecture would be tight even if H is a Hamiltonian path, as there are examples of a planar graph G and Hamiltonian path H in G for which BBC$_{2}$( G, H ) = 6 [12]. Problem 1 has also a version proposed by the same authors when H is restricted to be a matching, in which case the upper bound is conjectured to be 5 [12]. There is also another variation of Problem 1 for circular backbone colourings where the upper bound is 7 [16].

Some effort to solve Problem 1 and its variations has been done by different authors in the last decade. Campos et al. [13] confirmed that Problem 1 has a positive answer if H is a tree of diameter at most 4. For larger values of q , Havet et al. [16] proved that, if G is planar and H is a forest in G , then BBC$_{q}$( G, H ) ≤ q + 6 and that this is tight for q = 4. Regarding circular backbone colouring, Havet et al. [16] proved that if G is planar and H is a forest in G , then CBC$_{q}$( G, H ) ≤ 2 q + 4 and conjectured that this bound is not tight. This was latter verified by [5], that also presented partial results for the circular variant of Problem 1. Araujo et al. [4] proved bounds when G is a planar graph without cycles of length 4 or 5 and H is a spanning forest of G in the circular variant of Problem 1.

On the other hand, Problem 2 was not much studied in the literature. In case G is chordal and H is a Hamiltonian path of G , Broersma et al. [11] observed that BBC$_{2}$( G, H ) ≤ χ ( G )+4. Actually, the technique they used can be easily extended to prove that if G is chordal and H has degree at most c , then BBC$_{2}$( G, H ) ≤ ω ( G ) + 2 c . A particular case of chordal graphs
that has received some attention is the one of split graphs [20, 9, 21]. Salman [20] presented
tight upper bounds for $\text{BBC}_q(G, H)$ in function of $\chi(G)$ and $q$, when $G$ is split and $H$ is
a forest of stars. The authors in [9] proved similar bounds when $G$ is split and $H$ is a
matching in $G$. They also presented complexity results for the computation of $\text{BBC}_q(G, H)$
for arbitrary $G$ and $H$ being a matching. Turowski [21] showed bounds when $G$ is complete
and $H$ belongs to some classes, and also presented a polynomial-time algorithm to compute
$\text{BBC}_2(G, H)$ when $G$ is split and $H$ is a matching in $G$.

**Our contribution.** In this work, we present some partial results towards the resolution of Problem 2 by possibly constraining $G$ to some subclasses of chordal graphs and also releasing the constraint of $H$ to be a forest. We first consider the case of $H$ being bipartite. When $G$ is an interval graph in which each vertex belongs to at most two maximal cliques, we give a positive answer to Problem 2.

**Theorem 1.** Let $G$ be an interval graph such that every vertex belongs to at most 2 maximal cliques and let $H$ be a bipartite spanning subgraph of $G$. Then, $\text{BBC}_2(G, H) \le \omega(G) + 3$.

We then show that Theorem 1 does not extend to the more general case of $G$ being
chordal by exhibiting a family of chordal graphs $G$ with spanning bipartite subgraphs $H$
satisfying $\text{BBC}_2(G, H) \ge \frac{5}{3}\omega(G)$.

**Proposition 1.** For infinitely many values of $\omega$, there exists a chordal graph $G$ and a spanning bipartite subgraph $H$ of $G$ such that $\omega(G) = \omega$ and $\text{BBC}_2(G, H) \ge \frac{5}{3}\omega$.

We then consider the case of $H$ having bounded maximum average degree. Recall that
$\text{Ad}(H') = \frac{2|\text{E}(H')|}{|\text{V}(H')|}$ is the average degree of $H$ and that is $\text{Mad}(H) = \max\{\text{Ad}(H') \mid H' \subseteq H\}$
is its maximum average degree. Note also that forests have maximum average degree smaller
than 2. When $\text{Mad}(H) \le d$, we prove that $\text{BBC}_2(G, H) \le (1+o(1)) \cdot \omega(G)$.

**Theorem 2.** Let $d \in \mathbb{R}_+^*$. Let $G$ be any chordal graph and let $H$ be any subgraph of $G$ with $\text{Mad}(H) \le d$. Then, $\text{BBC}_2(G, H) \le \omega(G) + 2\sqrt{d \cdot \omega(G)} + 3d$.

We finally show that $\text{BBC}_2(G, H) \le \frac{3}{2}\omega(G) + \mathcal{O}(1)$ holds whenever $G$ is chordal and $H$ is $C_4$-free, which is thus halfway between Problem 2 and the trivial bound $\text{BBC}_2(G, H) \le 2\chi(G) - 1$. Recall that $H$ is $C_4$-free if $H$ does not contain $C_4$ as a subgraph (not necessarily induced).

**Theorem 3.** Let $G$ be a chordal graph and $H$ be a $C_4$-free spanning subgraph of $G$. Then, $\text{BBC}_2(G, H) \le \frac{3}{2}\omega(G) + 4$.

A tree-decomposition of $G$ is a pair $(T, \mathcal{X})$ where $T = (I, F)$ is a tree, and $\mathcal{X} = (B_i)_{i \in I}$ is a family of subsets of $V(G)$, called *bags* and indexed by the vertices of $T$, such that:

1. each vertex $v \in V$ appears in at least one bag, i.e. $\bigcup_{i \in I} B_i = V$,

2. for each edge $e = xy \in E$, there is an $i \in I$ such that $x, y \in B_i$, and
3. for each $v \in V$, the set of nodes indexed by $\{i \mid i \in I, v \in B_i\}$ forms a subtree of $T$.

The width of a tree decomposition is defined as $\max_{i \in I}\{|B_i| - 1\}$. The treewidth of $G$, denoted by $\text{tw}(G)$, is the minimum width of a tree-decomposition of $G$. It is well-known that every graph $G$ is a subgraph of a chordal graph $G'$ with $\omega(G') = \text{tw}(G) + 1$ (see for instance [14, Corollary 12.3.12]). Hence the following is a direct consequence of Theorems 2 and 3.

**Corollary 1.** Let $G$ be a graph and $H$ be a subgraph of $G$, then:

1. $\text{BBC}_2(G, H) \le \text{tw}(G) + \mathcal{O}(\sqrt{\text{Mad}(H) \cdot \text{tw}(G)})$, and

2. $\text{BBC}_2(G, H) \le \frac{3}{2}\text{tw}(G) + \frac{11}{2}$ if $H$ is $C_4$-free.

# 2 Our Contributions

For basic notions and terminology on Graph Theory not explicitly defined in this section, the reader is referred to [8]. Let $G$ be a graph and $X \subseteq V(G)$ be any subset of vertices. We denote by $N_G[X]$ the union of closed neighbourhoods in $X$, that is $N_G[X] = \bigcup_{x \in X} N[x]$, where $N[x]$ denotes $\{x\} \cup N(x)$.

A chordal graph is a graph without any induced cycle of length at least 4. A graph $G = (V, E)$ is an interval graph if there exists a set of intervals $\mathcal{I}$ on the real line and an injection $\iota: V \to \mathcal{I}$ such that, for every pair of vertices $u, v \in V$, $uv \in E$ if and only if $\iota(u) \cap \iota(v) \ne \emptyset$. It is well known that interval graphs are chordal (see [14, Exercise 5.42]), and that the converse is not true.

A path-decomposition is a tree-decomposition $(P, \mathcal{X})$ with the extra property that $P$ is a path. A clique $C$ of a graph $G$ is maximal if every vertex of $V(G) \setminus C$ is non-adjacent to at least one vertex in $C$. We skip the proof of the following well-known property of interval graphs (see for instance [14, Exercise 12.29]).

**Proposition 2.** Every interval graph $G$ admits a path-decomposition $(P, \mathcal{X} = (X_1, \dots, X_\ell))$ such that, for every $i \in [\ell]$, $X_i$ is a maximal clique of $G$.

## 2.1 Bipartite backbones

The goal of this section is to prove Theorem 1 and Proposition 1.

**Theorem 1.** Let $G$ be an interval graph such that every vertex belongs to at most 2 maximal cliques and let $H$ be a bipartite spanning subgraph of $G$. Then, $\text{BBC}_2(G, H) \le \omega(G) + 3$.

*Proof.* In this proof, since we will consider circular permutations of colours modulo $\omega(G)$, let us assume for better readability that the colours belong to $\{0, \dots, \omega(G) - 1\}$ and that all arithmetic operations with colours must be understood modulo $\omega(G)$. A circular interval, denoted by $[a, b]$, is the interval $[a, a + 1, \dots, b - 1, b]$ if $0 \le a \le b < \omega(G)$ and it is equal to $[a, a + 1, \dots, \omega(G) - 1, 0, \dots, b]$ if $0 \le b < a < \omega(G)$. With a slight abuse of notation, when
it is convenient, we consider circular intervals as sets, otherwise as sequences of consecutive non-negative integers (modulo $\omega(G)$). In particular, we consider that circular intervals are always represented in clockwise order.

Let $(A, B)$ be a bipartition of $H$, and $(X_1, \cdots, X_\ell)$ be a path-decomposition of $G$ such that $X_i$ is a maximal clique for every $1 \le i \le \ell$, the existence of which is guaranteed by Proposition 2. Without loss of generality, we assume that each $X_i$ has size exactly $\omega(G)$. Indeed, if this is not the case, for each $i \in [t]$ we add $\omega(G) - |X_i|$ new pairwise adjacent vertices dominating $X_i$ and these new vertices belong to $A$ and are isolated vertices in $H$. In what follows, we further let $X_0 = X_{\ell+1} = \emptyset$.

By assumption, $X_{i-1} \cap X_{i+1} = \emptyset$ for every $1 < i < \ell$. Moreover, for every $1 \le i \le \ell$, let $A_i = X_{i-1} \cap X_i \cap A$, $B_i = X_{i-1} \cap X_i \cap B$, $A'_i = X_i \cap A \setminus (X_{i-1} \cup X_{i+1})$ (i.e., $A'_i$ is the set of the simplicial vertices of $X_i \cap A$) and $B'_i = X_i \cap B \setminus (X_{i-1} \cup X_{i+1})$. Note that $A_1 = B_1 = \emptyset$. Note also that $\{A_i, A'_i, A_{i+1}\}$ is a partition of $X_i \cap A$, possibly with empty parts, while the same happens for $\{B_i, B'_i, B_{i+1}\}$ with respect to $X_i \cap B$, for every $1 \le i \le \ell$. See Figure 1.

<figure><img src="image_2.png" /><figcaption>Figure 1: Representation of sets used in the proof of Theorem 1</figcaption></figure>

We start by building a proper $\omega(G)$-colouring $\varphi : V(G) \to \{0, \cdots, \omega(G) - 1\}$ of $G$ with the following properties: for every $1 \le i \le \ell$,

* $\varphi(X_i) = \{0, \cdots, \omega(G) - 1\}$;

* $\varphi(A \cap X_i)$ and $\varphi(B \cap X_i)$ are two circular intervals that partition $\{0, \cdots, \omega(G) - 1\}$.

* $\varphi(A \cup X_i)$ is the concatenation of the three circular intervals $\varphi(A_i), \varphi(A'_i)$ and $\varphi(A_{i+1})$ (in this order if $i$ is odd and in the reversed order if $i$ is even), and

* $\varphi(B \cup X_i)$ is the concatenation of the three circular intervals $\varphi(B_i), \varphi(B'_i)$ and $\varphi(B_{i+1})$ (in this order if $i$ is even and in the reversed order if $i$ is odd).

To show that such a colouring $\varphi$ exists, we inductively build its restriction $\varphi_i$ to $G[\bigcup_{j \le i} X_j]$ for each $i$ from 1 to $\ell$ (obviously $\varphi_\ell = \varphi$).

Let $\varphi_1$ be defined as follows:

* If $X_i \cap A = \emptyset$, then $\varphi_1$ colours the vertices of $B'_1$ with colours 0 to $|B'_1| - 1$, and then vertices of $B_2$ with colours $|B'_1|$ to $|B'_1| + |B_2| - 1 = |X_1| - 1 = \omega(G) - 1$.
• Otherwise, $\varphi_1$ colours the vertices of $A'_1$ with colours 0 to $|A'_1| - 1$, and then vertices of $A_2$ with colours $|A'_1|$ to $|A'_1| + |A_2| - 1 = |A \cap X_1| - 1$. Then, $\varphi_1$ colours the vertices of $B_2$ from colour $|A \cap X_1|$ to $|A \cap X_1| + |B_2| - 1$ and then vertices of $B'_1$ from $|A \cap X_1| + |B_2|$ to $|A \cap X_1| + |B_2| + |B'_1| - 1 = |X_1| - 1 = \omega(G) - 1$.

In this case, let denote by $v_1$ (resp., by $v'_1$) the vertex of $A \cap X_1$ coloured with colour 0 (resp., the vertex of $A \cap X_1$ coloured with colour $|A \cap X_1| - 1$). Possibly $v_1 = v'_1$.

Now, let us assume that $\varphi_{i-1}$ has been defined recursively for some $1 < i \le l$, and that, by induction, there exist colours $x_i, y_i, c_i \in \{0, \dots, \omega(G) - 1\}$ and $c_i \in [x_i, y_i]$, such that:

• either $A_i = \emptyset$ and $\varphi_{i-1}(B_i) = [x_i, y_i]$, or $B_i = \emptyset$ and $\varphi_{i-1}(A_i) = [x_i, y_i]$ (note that $A_i \cup B_i \ne \emptyset$ since $G$ is connected), or

• $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ and $\varphi_{i-1}(A_i) = [x_i, c_i]$ and $\varphi_{i-1}(B_i) = [c_i + 1, y_i]$, or vice-versa:

• $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ and $\varphi_{i-1}(B_i) = [x_i, c_i - 1]$ and $\varphi_{i-1}(A_i) = [c_i, y_i]$.

We extend $\varphi_{i-1}$ to $\varphi_i$ as follows. Obviously, for every $v \in \bigcup_{0 \le j < i} X_j$, $\varphi_i(v) = \varphi_{i-1}(v)$. For the vertices of $X_i \setminus X_{i-1}$, there are the following cases to be considered:

• First let us consider the case when $A \cap (X_i \setminus X_{i-1}) = A'_i \cup A_{i+1} = \emptyset$.

– If $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ is the concatenation of the interval $\varphi_{i-1}(A_i)$ and $\varphi_{i-1}(B_i)$ (in this order) and possibly $A_i$ or $B_i$ being empty, then $\varphi_i$ colours the vertices of $B'_i$ with colours from $y_i + 1$ to $y_i + |B'_i|$ and then $\varphi_i$ colours the vertices of $B_{i+1}$ with colours from $y_i + |B'_i| + 1$ to $y_i + |B'_i| + |B_{i+1}| = x_i - 1$ (modulo $\omega(G)$). (the last equality comes from the fact that $|A_i \cup B_i| = |X_i \cap X_{i-1}| = |[x_i, y_i]|$ and $\omega(G) = |X_i| = |X_i \cap X_{i-1}| + |B'_i| + |B_{i+1}|$.)

– Otherwise, $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ is the concatenation of the interval $\varphi_{i-1}(B_i)$ and $\varphi_{i-1}(A_i)$ (in this order). Then $\varphi_i$ colours the vertices of $B_{i+1}$ with colours from $y_i + 1$ to $y_i + |B_{i+1}|$ and then $\varphi_i$ colours the vertices of $B'_i$ with colours from $y_i + |B_{i+1}| + 1$ to $y_i + |B_{i+1}| + |B'_i| = x_i - 1$ (modulo $\omega(G)$).

• Otherwise, $A \cap (X_i \setminus X_{i-1}) = A'_i \cup A_{i+1} \ne \emptyset$.

– If $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ is the concatenation of the interval $\varphi_{i-1}(A_i)$ and $\varphi_{i-1}(B_i)$ (in this order) and possibly $A_i$ or $B_i$ is empty, then $\varphi_i$ colours the vertices of $B'_i$ with colours from $y_i + 1$ to $y_i + |B'_i|$ and then $\varphi_i$ colours the vertices of $B_{i+1}$ with colours from $y_i + |B'_i| + 1$ to $y_i + |B'_i| + |B_{i+1}|$. Then, $\varphi_i$ colours the vertices of $A_{i+1}$ with colours from $y_i + |B'_i| + |B_{i+1}| + 1$ to $y_i + |B'_i| + |B_{i+1}| + |A_{i+1}|$ and then $\varphi_i$ colours $A'_i$ with colours from $y_i + |B'_i| + |B_{i+1}| + |A_{i+1}| + 1$ to $y_i + |B'_i| + |B_{i+1}| + |A_{i+1}| + |A'_i| = x_i - 1 \bmod \omega(G)$. See Figure 2(b).

(the last equality comes from the fact that $|A_i \cup B_i| = |X_i \cap X_{i-1}| = |[x_i, y_i]|$ and $\omega(G) = |X_i| = |X_i \cap X_{i-1}| + |X_i \setminus X_{i-1}|$ and $X_i \setminus X_{i-1} = A'_i \cup A_{i+1} \cup B'_i \cup B_{i+1}$.)
- If $\varphi_{i-1}(A_i \cup B_i) = [x_i, y_i]$ is the concatenation of the interval $\varphi_{i-1}(B_i)$ and $\varphi_{i-1}(A_i)$ (in this order), then $\varphi_i$ colours the vertices of $A_i'$ with colours from $y_i + 1$ to $y_i + |A_i'|$ and then $\varphi_i$ colours the vertices of $A_{i+1}$ with colours from $y_i + |A_i'| + 1$ to $y_i + |A_i'| + |A_{i+1}|$. Then, $\varphi_i$ colours the vertices of $B_{i+1}$ with colours from $y_i + |A_i'| + |A_{i+1}| + 1$ to $y_i + |A_i'| + |A_{i+1}| + |B_{i+1}|$ and finally $\varphi_i$ colours $B_i'$ with colours from $y_i + |A_i'| + |A_{i+1}| + |B_{i+1}| + 1$ to $y_i + |A_i'| + |A_{i+1}| + |B_{i+1}| + |B_i'| = x_i - 1$ (modulo $\omega(G)$). See Figure 2(a).

Defined that way, we have that $\varphi_i(A \cap X_i) = [\alpha_i, \beta_i]$. Let $v_i$ (resp., $v_i'$) be the vertex of $A \cap X_i$ coloured with colour $\alpha_i$ (resp., with colour $\beta_i$).

<figure><img src="image_3.png" /><figcaption>Figure 2: Colours' ordering for vertices in $X_i$ in the proof of Theorem 1</figcaption></figure>

The function $\varphi$ that we defined above is clearly a $\omega(G)$-proper colouring of $G$ satisfying the announced properties.

To obtain the desired 2-backbone ($\omega(G)+3$)-colouring $\varphi'$ of $(G, H)$, let us start from a colouring $\varphi' = \varphi$. Now, note that the set $X = \bigcup_{1 \le i \le l} \{v_i, v_i'\} \subseteq A$ induces a set of disjoint paths in $G$. Indeed, each clique $X_i$ contains at most two vertices of $X$ ($v_i$ and/or $v_i'$), and, for $v \in \{v_i, v_i'\}$, if $v \in X_i \cap X_{i-1}$, then $v \in \{v_{i-1}, v_{i-1}'\}$. We modify $\varphi'$ by recolouring vertices in $X$ in such a way that $\varphi'$ induces a proper colouring of $G[X]$ using colours $\{\omega(G)+1, \omega(G)+2\}$.

Note that $\varphi'$ now is a proper ($\omega(G)+3$)-colouring of $G$. Now, let $\{u, v\} \in E(H)$ and let $1 \le i \le l$ such that $u \in X_i \cap A$ and $v \in X_i \cap B$. By construction of $\varphi$, the colour $\varphi(v) = \varphi'(v)$ is at distance 2 from $\varphi(w) = \varphi'(w)$ for every $w \in X_i \cap A \setminus \{v_i, v_{i+1}\}$. Moreover, $\{\varphi'(v_i), \varphi'(v_{i+1})\} = \{\omega(G)+1, \omega(G)+2\}$ and $\varphi'(v) < \omega(G)$. Hence, the distance between $\varphi'(u)$ and $\varphi'(v)$ is at least two. So $\varphi'$ is a 2-backbone ($\omega(G)+3$)-colouring of $(G, H)$. This concludes the proof. $\square$
In the sequel, we show that the upper bound provided by Theorem 1 cannot be extended to the more general case of G being chordal.

**Proposition 1.** For infinitely many values of $\omega$, there exists a chordal graph G and a spanning bipartite subgraph H of G such that $\omega(G) = \omega$ and $\text{BBC}_2(G, H) \ge \frac{5}{3}\omega$.

*Proof.* Let us first build G and H as required. Let $r \in \mathbb{N}$ be any positive integer and define $\omega = 3r$. To build G, we start with a complete graph $K_\omega$. We refer to this initial set of vertices as K. Then, for any $X \subseteq K$ of size $|X| = r$, add a complete graph $K_{2r}$ on $2r$ new vertices and make them adjacent to all vertices in X. For each X, we refer to such $2r$ vertices as $K_X$. It is straightforward to check that G is chordal.

Let H be the bipartite graph induced by the edges linking the vertices in K to the ones in $K_X$, for all $X \subseteq K$ with $|X| = r$. Note that K is an independent set in H, as well as the union of the vertices in $K_X$, over all $X \subseteq K$ with $|X| = r$. Thus, H is bipartite.

Let $\varphi$ be a 2-backbone k-colouring of $(G, H)$. Note that a vertex $v \in K$ with colour $1 < a < k$ forbids not only colour a, but also colours $a-1$ and $a+1$ from appearing in its neighbourhood in H. Since K induces a complete graph on G, in $\varphi$ there are $\omega$ distinct colours $1 \le c_1 < c_2 < \dots < c_\omega \le k$ in K. Let X be the set of vertices $v \in K$ such that $\varphi(v) = c_{3p+2}$ for some $p \in \{0, \dots, r-1\}$. Note that $|X| = r$ and each vertex in X forbids a distinct set of exactly three colours from appearing in all vertices in $K_X$ in the 2-backbone k-colouring c. Consequently, $\varphi$ uses at least $3r + 2r = \omega + 2r$ colours as $K_X$ induces a complete graph on $2r$ vertices. This shows that $\text{BBC}_2(G, H) \ge \frac{5}{3}\omega$, as desired. $\square$

## 2.2 Sparse backbones

This section is devoted to the proof of Theorem 2.

**Theorem 2.** Let $d \in \mathbb{R}_+^*$. Let G be any chordal graph and let H be any subgraph of G with $\text{Mad}(H) \le d$. Then, $\text{BBC}_2(G, H) \le \omega(G) + 2\sqrt{d \cdot \omega(G)} + 3d$.

*Proof.* Fix $d \in \mathbb{R}_+^*$. Let us show a stronger statement that, for every $\varepsilon > 0$, every chordal graph G, and every spanning subgraph H of G with $\text{Mad}(H) \le d$, we have

$$ \text{BBC}_2(G, H) \le (1 + \varepsilon)\omega(G) + c_{\varepsilon,d}, $$

where $c_{\varepsilon,d} = \max \left\{ \frac{d}{\varepsilon}, \frac{d}{2\varepsilon} + 3d \right\} \le \frac{d}{\varepsilon} + 3d$. In particular, by setting $\varepsilon = \sqrt{\frac{d}{\omega(G)}}$, we obtain

$$ \begin{aligned} \text{BBC}_2(G, H) &\le (1 + \varepsilon)\omega(G) + \frac{d}{\varepsilon} + 3d \le \left(1 + \sqrt{\frac{d}{\omega(G)}}\right)\omega(G) + \frac{d}{\sqrt{\frac{d}{\omega(G)}}} + 3d \\ &\le \omega(G) + 2\sqrt{d \cdot \omega(G)} + 3d. \end{aligned} $$

Fix a real $\varepsilon > 0$ and let $c_{\varepsilon,d}$ be as defined above. We will show by induction on the order $n = |V(G)| = |V(H)|$ of G that $\text{BBC}_2(G, H) \le (1 + \varepsilon)\omega(G) + c_{\varepsilon,d}$. For better readability, in what follows, we denote $\omega(G)$ by $\omega$ and we fix $k$ to $\lfloor(1 + \varepsilon)\omega + c_{\varepsilon,d}\rfloor$.
Assume first that $n \le \frac{d}{\epsilon}$. In this case, it is sufficient to prove that $BBC_2(G, H) \le 2\omega$ as $2\omega \le \omega + n \le k$. We are thus done by (1). Henceforth we assume that $n > \frac{d}{\epsilon}$ and that the result holds for any chordal graph $G'$ with at most $n-1$ vertices and any spanning subgraph $H' \subseteq G'$ satisfying $\mathrm{Mad}(H') \le d$.

If $G$ has a vertex $v \in V(G)$ such that $\mathrm{deg}_G(v) + 2\mathrm{deg}_H(v) < k$, let $G' = G - v$ and $H' = H - v$. Note that $G'$ is chordal, $\omega(G') \le \omega$, and $H'$ is a spanning subgraph of $G'$ satisfying $\mathrm{Mad}(H') \le \mathrm{Mad}(H) \le d$. By induction hypothesis, let $\varphi'$ be a 2-backbone $k$-colouring of $(G', H')$. By the assumption on the degree of $v$ in $G$ and in $H$, at least one colour of $\{1, \dots, k\}$ remains valid to colour $v$ and extend $\varphi'$ into a 2-backbone $k$-colouring of $(G, H)$. This shows that the result holds if $G$ contains such a vertex. Consequently, let us assume that, for every vertex $v \in V(G)$, that

$$ \mathrm{deg}_G(v) + 2\mathrm{deg}_H(v) \ge k > (1 + \epsilon)\omega + c_{\epsilon,d} - 1. \quad (4) $$

In the sequel, we prove that this case cannot occur, by the choice of $c_{\epsilon,d}$, which concludes the proof.

For an ordering $(v_1, \dots, v_n)$ over $V(G)$, define $X_i = \{v_j \mid 1 \le j \le i\}$ and $W_i = N_G[X_i]$. As shown in [7, Lemma 14], there exists an ordering $(v_1, \dots, v_n)$ over $V(G)$ such that, for all integers $1 \le i \le n$:

$$ \mathrm{deg}_G(v_i) \le i + \omega - 2, \text{ and} \quad (5) $$

$$ |W_i| \le 2i + \omega - 1. \quad (6) $$

From (4) and (5), it follows that, for every integer $1 \le i \le n$:

$$ \begin{aligned} 2 \sum_{1 \le j \le i} \mathrm{deg}_H(v_j) &= \sum_{1 \le j \le i} 2 \mathrm{deg}_H(v_j) > \sum_{1 \le j \le i} ((1 + \epsilon)\omega + c_{\epsilon,d} - 1 - \mathrm{deg}_G(v_j)) \\ &\ge \sum_{1 \le j \le i} ((1 + \epsilon)\omega + c_{\epsilon,d} - 1 - (j + \omega - 2)) \\ &= \sum_{1 \le j \le i} (\epsilon\omega + c_{\epsilon,d} - j + 1) \\ &= i\epsilon\omega + ic_{\epsilon,d} - \frac{i(i-1)}{2}. \end{aligned} \quad (7) $$

On the other hand, since $H$ satisfies $\mathrm{Mad}(H) \le d$, we have that $2|E(H')| \le d|V(H')|$, for any $H' \subseteq H$. Then, note that (6) implies

$$ 2 \sum_{1 \le j \le i} \mathrm{deg}_H(v_j) \le 2(|E(H[W_i])| + |E(H[X_i])|) \le d(|W_i| + |X_i|) \le d(3i + \omega - 1). \quad (8) $$

Hence, by (7) and (8), for every integer $1 \le i \le n$, we have $i\epsilon\omega + ic_{\epsilon,d} - \frac{i(i-1)}{2} < d(3i+\omega-1)$, which implies that $c_{\epsilon,d} < 3d - \epsilon\omega + \frac{d\omega}{i} + \frac{(i-1)}{2} - \frac{d}{i}$. Recall that $n \ge \frac{d}{\epsilon}$. Therefore, applied $i = \lfloor \frac{d}{\epsilon} \rfloor$, the previous inequality implies that $c_{\epsilon,d} < 3d + \frac{d}{2\epsilon}$. This contradicts our choice of $c_{\epsilon,d}$. $\square$
As mentioned in the introduction, we thus obtain the following when $H$ is a forest.

**Corollary 2.** If $G$ is chordal and $H$ is a forest, then $\text{BBC}_2(G, H) \le \omega(G) + \mathcal{O}(\sqrt{\omega(G)})$.

*Proof.* It is a direct consequence of Theorem 2 as $\text{Mad}(T) < 2$ holds for any tree $T$. $\square$

## 2.3 Backbones without 4-cycles

This section is devoted to the proof of Theorem 3.

**Theorem 3.** Let $G$ be a chordal graph and $H$ be a $C_4$-free spanning subgraph of $G$. Then, $\text{BBC}_2(G, H) \le \frac{3}{2}\omega(G) + 4$.

*Proof.* Assume first that $\omega(G) = \omega$ is odd. There exists (see [7, Lemma 12]) a tree-decomposition $(T, \mathcal{X})$ of $G$ such that $T$ is rooted in $r \in V(T)$ and, $|X_v| = \omega$ for all $v \in V(T)$ and, for every $v \in V(T) \setminus \{r\}$ with parent $p$, $|X_p \setminus X_v| = |X_v \setminus X_p| = 1$.

In [7] (proof of Theorem 7), it was further shown that there exists a proper colouring $\varphi: V \to \{1, \dots, \frac{\omega+3}{2}\}$ such that, for each $t \in V(T)$, every colour appears at most twice in $X_t$ and at most three colours appear uniquely in $X_t$. Moreover, using the fact that $H$ is $C_4$-free, two vertices that are adjacent in $H$ are assigned distinct colours.

This implies that $V(G)$ can be partitioned into $k \le \frac{\omega+3}{2}$ induced forests $F_1, \dots, F_k$. For every $1 \le i \le k$, proper colour the vertices of $F_i$ using colours $3i-1$ and $3i-2$. This is clearly a proper colouring of $G$. Moreover, for every $\{u, v\} \in E(H)$, $u$ and $v$ are in distinct forests and so, their colours differ by at least 2. Hence, $\text{BBC}_2(G, H) \le 3\frac{\omega+3}{2} - 1 = \frac{3\omega+7}{2}$.

Finally, if $\omega$ is even, we apply previous paragraph to $G-I$ (where $I$ is an independent set with $\omega(G-I) = \omega(G) - 1$) and add two extra colours for $I$. We thus obtain

$$ \text{BBC}_2(G, H) \le \frac{3(\omega - 1) + 7}{2} + 2 = \frac{3\omega + 8}{2}, $$

as desired. $\square$

## 3 Further Research

In this paper, we prove several evidences for the following conjecture, which is still open.

**Conjecture 1.** Let $G$ be a chordal graph and $H$ be a spanning forest of $G$. Then

$$ \text{BBC}_2(G, H) \le \omega(G) + \mathcal{O}(1). $$

We actually believe that even the following much stronger one holds.

**Conjecture 2.** There exists a function $f: \mathbb{N}^2 \to \mathbb{N}$ such that the following holds. For every chordal graph $G$ and every subgraph $H$ of $G$, if $\text{Mad}(H) \le d$ then

$$ \text{BBC}_q(G, H) \le \omega(G) + f(q, d). $$
When $H$ is bipartite, the following problem is open. The fact that $\frac{5}{3} \le \gamma \le 2$ follows from (1) and Proposition 1.

**Problem 3.** Find the infimum of all values $\frac{5}{3} \le \gamma \le 2$ for which $X$ is infinite, where

$$X = \{\omega(G) \mid \exists G \text{ chordal, } H \text{ bipartite, } H \subseteq G, \mathrm{BBC}_2(G, H) \ge \gamma \cdot \omega(G)\}.$$

## References

[1] K. I. Aardal, S. P. M. Hoesel, A. M. C. A. Koster, C. Mannino, and A. Sassano. Models and solution techniques for frequency assignment problems. *Annals of Operations Research*, 153(1):79–129, 2007.

[2] K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging. *Illinois J. Math.*, 21(3):429–490, 09 1977.

[3] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. Part II: Reducibility. *Illinois J. Math.*, 21(3):491–567, 09 1977.

[4] J. Araujo, F. Havet, and M. Schmitt. Steinberg-like theorems for backbone colouring. *Electronic Notes in Discrete Mathematics*, 50:223–229, 2015.

[5] C. S. Araújo, J. Araújo, A. Silva, and A. A. Cezar. Backbone coloring of graphs with galaxy backbones. *Discrete Applied Mathematics*, 323:2–13, 2022.

[6] J. Araújo, R. Castro, and A. Talon. About directed backbone colourings of graphs. In *Annals of the 11th Latin American Workshop on Cliques in Graphs*, page 26, 2024.

[7] S. Bessy, F. Havet, and L. Picasarri-Arrieta. Dichromatic number of chordal graphs. *Graphs and Combinatorics*, 41(4):81, 2025.

[8] J. A. Bondy and U. S. R. Murty. *Graph Theory*. Springer, 2008.

[9] H. Broersma, B. Marchal, D. Paulusma, and A. Salman. Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. *Discussiones Mathematicae Graph Theory*, 29(1):143–162, 2009.

[10] H. J. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger. Backbone colorings for networks. In H. L. Bodlaender, editor, *Graph-Theoretic Concepts in Computer Science*, pages 131–142. Springer, 2003.

[11] H. J. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger. Backbone colorings for graphs : tree and path backbone. *Journal of Graph Theory*, 55(2):137–152, 2007.

[12] H. J. Broersma, J. Fujisawa, and K. Yoshimoto. Backbone colorings along perfect matchings. Technical Report 1706, University of Twente, 2003.
[13] V. Campos, F. Havet, R. Sampaio, and A. Silva. Backbone colouring: Tree backbones with small diameter in planar graphs. *Theoretical Computer Science*, 487:50-64, 2013.

[14] R. Diestel. *Graph Theory*. Graduate texts in mathematics. Springer, 5th edition, 2017.

[15] F. Havet and A. D. King. List circular backbone colouring. *Discrete Mathematics and Theoretical Computer Science*, 16(1):89-104, 2014.

[16] F. Havet, A. D. King, M. Liedloff, and I. Todinca. (Circular) backbone colouring: Forest backbones in planar graphs. *Discrete Applied Mathematics*, 169:119-134, 2014.

[17] T. R. Jensen and B. Toft. *Graph Coloring Problems*. Wiley-Interscience, 1995.

[18] R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, *Complexity of Computer Computations*, pages 85-103. Plenum Press, 1972.

[19] M. Molloy and B. Reed. *Graph Colouring and the Probabilistic Method*. Springer, 2001.

[20] A. N. M. Salman. λ-backbone coloring numbers of split graphs with tree backbones. In *Proceeding of The Second IMT-GT 2006 Regional Conference on Mathematics, Statistics and Applications*, pages 43-47, 2006.

[21] K. Turowski. Optimal backbone coloring of split graphs with matching backbones. *Discussiones Mathematicae Graph Theory*, 35(1):157-169, 2015.