Paper Info
Title
The Local Nature of List Colorings for Graphs of High Girth
Abstract
We consider list coloring problems for graphs $\mathcal{G}$ of girth larger than $c\log_{\Delta-1}n$, where $n$ and $\Delta\geq3$ are, respectively, the order and the maximum degree of $\mathcal{G}$, and $c$ is a suitable constant. First, we determine that the edge and total list chromatic numbers of these graphs are $\chi'_l(\mathcal{G})=\Delta$ and $\chi”_l(\mathcal{G})=\Delta+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\log_{k-1}n$.
Year
DOI
Venue
2010
10.1007/978-3-540-70575-8_27
SIAM Journal on Computing
Keywords
DocType
Volume
optimal list colorings,maximum degree,general conjectures ofbollob,particular classof graph,proofs exhibit,high girth,list colorings,c log,local nature,clogk-1 n,certain degree,k-list vertex colorings,total list chromatic number,algorithms,graph coloring,list coloring
Journal
39
Issue
ISSN
Citations 
6
0302-9743
1
PageRank 
References 
Authors
0.37
18
2
Name
Order
Citations
PageRank
Flavio Chierichetti162639.42
Andrea Vattani217111.45