Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423410 | Discrete Mathematics | 2013 | 6 Pages |
For 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.