UniquelyH-colorable graphs with large girth
Xuding Zhu · Journal of Graph Theory · 1996
Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition σ ??? c of c with an automorphism σ of H. In case H is the complete graph Kn, the notion of uniquely H-colorable coincides with that of uniquely n-colorable. It was proved by B. Bollobás and N. Sauer that for any integer n there are graphs of arbitrary large girth which are uniquely n-colorable. We generalize this result and prove that for any graph H which is a core (i.e., H admits no homomorphisms to any of its proper subgraphs), and for any integer g, there is a graph which is uniquely H-colorable and has girth at least g. We then use this generalization to answer a question concerning the star-chromatic number of a graph. A graph G is said to be (k,d)-colorable if there is a coloring c of the vertices of G with k colors {0,1,…,k − 1} such that d ≤ |c(x)−c(y)| ≤ k − d for every edge (x,y) of G. The star-chromatic number of G is the infimum of the ratio k/d such that G is (k,d)-colorable. We shall show that for any rational k/d ≥ 2, there are graphs G of arbitrary large girth with star-chromatic number χ*(G) = k/d. In particular, for any integer n, there are graphs G of arbitrary large girth with χ*(G) = χ(G)=n. © 1996 John Wiley & Sons, Inc.