×

On the list coloring version of Reed’s conjecture. (English) Zbl 1378.05054

Drmota, Michael (ed.) et al., Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 61, 343-349 (2017).
Summary: The chromatic number of a graph is bounded below by its clique number and from above by its maximum degree plus one. B. Reed [J. Graph Theory 27, No. 4, 177–212 (1998; Zbl 0980.05026)] conjectured that the chromatic number is at most halfway in between these trivial lower and upper bounds. Moreover, Reed [loc. cit.] proved that its at most some non-trivial convex combination of the two bounds. A. D. King and B. A. Reed [ibid. 81, No. 1, 30–34 (2016; Zbl 1330.05070)] produced a short proof that, provided the maximum degree is large enough, a combination of 1/130,000 suffices. Recently M. Bonamy, T. Perrett and L. Postle [“Colouring graphs with sparse neighbourhoods: bounds and applications” (submitted)] improved this to 1/26.
It is natural to wonder if similar results hold for the list chromatic number. Unfortunately, previous techniques for ordinary coloring do not extend to list coloring. In this paper, we overcome these hurdles by introducing several new ideas. Our main result is that the list chromatic number is at most some non-trivial convex combination of the clique number and the maximum degree plus one. Furthermore, we show that for large enough maximum degree, that a combination of 1/13 suffices. Note that this also improves on the best known results for ordinary coloring.
For the entire collection see [Zbl 1375.05004].

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Bonamy, T. Perrett, L. Postle, Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications, Submitted, 2016.; M. Bonamy, T. Perrett, L. Postle, Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications, Submitted, 2016.
[2] Bruhn, H.; Joos, F., A stronger bound for the strong chromatic index · Zbl 1378.05047
[3] King, A. D., Hitting all maximum cliques with a stable set using lopsided independent transversals, J. Graph Theory, 67, 4, 300-305 (2011) · Zbl 1231.05205
[4] King, A. D.; Reed, B. A., A short proof that \(χ\) can be bounded \(ε\) away from \(\Delta + 1\) towards \(ω\), J. Graph Theory, 81, 1, 30-34 (2016) · Zbl 1330.05070
[5] Molloy, M.; Reed, B. A., A bound on the strong chromatic index of a graph, J. Combin. Theory, Ser. B, 69, 2, 103-109 (1997) · Zbl 0880.05036
[6] Reed, B. A., \(ω\), Δ, and \(χ\), J. Graph Theory, 27, 4, 177-212 (1998) · Zbl 0980.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.