Originator(s): Van Vu (UCSD, vanvu@ucsd.edu)
Definitions: The codegree of two vertices u and v in a graph is their number of common neighbors. Small codegree is a "local" version of sparseness.
Question: Let c be a fixed small positive constant. Let G be a graph with maximum degree D and maximum codegree at most cD. Is it true that the list chromatic number of G is at most (c+o(1))D? Here o(1) tends to zero as D tends to infinity.
Background/motivation:
Comments/Partial results: If true this conjecture would imply a well known result of Kahn on the list chromatic index of linear hypergraphs. (This is an exercise.) Kahn's result implies an assymptotic version of the Erdos-Faber-Lov\'asz Conjecture.
There are some related results in the reference, but even the following is not known: Let c be a fixed small positive constant. Let G be a graph with maximum degree D and maximum codegree at most cD. Is it true that G has an independent set of size at least n(G)/1000cD? Here 1000, of course, means a large absolute constant.
References:
V. Vu, A general upper bound on the list chromatic number of locally sparse
graphs, Combinatorics, Probability and Computing (2002), 11, 103-111.