Backbone coloring for graphs with large girths

AbstractFor a graph G and a subgraph H (called a backbone graph) of G, a backbonek-coloring ofGwith respect toH is a proper vertex coloring of G using colors from the set {1,2,…,k}, with an additional condition that colors for any two adjacent vertices in H must differ by at least two. The backbone chromatic number ofGoverH, denoted by BBC(G,H), is the smallest k of a backbone k-coloring admitted by G with respect to H. Broersma, Fomin, Golovach, and Woeginger (2007) [2] showed that BBC(G,H)≤2χ(G)−1 holds for every G and H; moreover, for every n there exists a graph G with a spanning tree T such that χ(G)=n and the bound is sharp. To answer a question raised in Broersma et al. (2007) [2], Miškuf, Škrekovski, and Tancer (2009) [16] proved that for any n there exists a triangle-free graph G with a spanning tree T such that χ(G)=n and BBC(G,T)=2n−1. We extend this result by showing that for any positive integers n and l, there exists a graph G with a spanning tree T such that G has girth at least l, χ(G)=n, and BBC(G,T)=2n−1