A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs

Source abstract

Suppose that G is a graph with maximum degree d ( G ) such that, for every vertex v in G , the neighbourhood of v contains at most d ( G ) 2 / f ( f > 1) edges. We show that the list chromatic number of G is at most Kd ( G )/log f , for some positive constant K . This result is sharp up to the multiplicative constant K and strengthens previous results by Kim [9], Johansson [7], Alon, Krivelevich and Sudakov [3], and the present author [18]. This also motivates several interesting questions. As an application, we derive several upper bounds for the strong (list) chromatic index of a graph, under various assumptions. These bounds extend earlier results by Faudree, Gyárfás, Schelp and Tuza [6] and Mahdian [13] and determine, up to a constant factor, the strong (list) chromatic index of a random graph. Another application is an extension of a result of Kostochka and Steibitz [10] concerning the structure of list critical graphs.