THE LOCAL NATURE OF LIST COLORINGS FOR GRAPHS OF HIGH GIRTH
We consider list coloring problems for graphs G of girth larger than c log(Delta-1) n, where n and Delta >= 3 are, respectively, the order and the maximum degree of G, and c is a suitable constant. First, we determine that the edge and total list chromatic numbers of these graphs are X(l)' (G) = Delta and X(l)'' (G) = Delta + 1. This proves that the general conjectures of Bollobas and Harris [Graphs Combin., 1 (1985), pp. 115-127], Behzad [The total chromatic number, in Combinatorial Mathematics and Its Applications (Proc. Conf., Oxford, 1969), Academic Press, London, 1971, pp. 1-8], Vizing [Diskret. Analiz., 3 (1964), pp. 25-30], and Juvan, Mohar, and. Skrekovski [Combin. Probab. Comput., 7 (1998), pp. 181-188] hold for this particular class of graphs. Moreover, our proofs exhibit a certain degree of "locality," which we exploit to obtain an efficient distributed algorithm able to compute both kinds of optimal list colorings. Also, using an argument similar to one of Erdos, we show that our algorithm can compute k-list vertex colorings of graphs having girth larger than c log(k-1) n.
girth algorithms graph coloring