Backbone colouring of chordal graphs

A proper k -colouring of a graph G = (V, E) is a function c : V(G) → {1,..., k} such that c(u) ≠ c(v) for every edge uv ∈ E(G). The chromatic number χ(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) | ≥ q for every edge uv ∈ 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. [12] ask whether, for any chordal graph G and any spanning forest H of G , we have that BBC 2 ( G, H) ≤ χ( 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)≥5χ(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)≤χ(G) + O(√χ(G)). We finally show that BBC 2 (G,H) ≤ 3/2χ(G) + O(1) holds whenever G is chordal and H is C 4 -free.