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Δ-1 n, where n and Δ ≥ 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) = Δ and X″l(G) = Δ + 1. This proves that the general conjectures of Bollobás 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 Škrekovski [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 Erdös, we show that our algorithm can compute k-list vertex colorings of graphs having girth larger than c logk-1 n. © 2010 Society for Industrial and Applied Mathematics.