Backbone coloring for graphs with large girths
Yuehua Bu, Daphne Der‐Fen Liu, Xuding Zhu · Discrete Mathematics · 2013
For a graph G and a subgraph H (called a backbone graph) of G , a backbone k -coloring of G with respect to H 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 of G over H , 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 ) = 2 n − 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 ) = 2 n − 1 .