zbMATH — the first resource for mathematics

A new upper bound for the list chromatic number. (English) Zbl 0674.05027
In this paper it is proved, using some arguments from the theory of random graphs, that if \(\Delta\) is sufficiently large, then for every graph G with maximum degree \(\Delta (G)=\Delta\), we have \(\chi '_{\ell}(G)\leq 7\Delta /4+\lceil 25\) log \(\Delta\) \(\rceil.\)
The authors assert that it is possible to give a slightly improved value for the above upper bound for the list chromatic number, namely \(\chi '_{\ell}(G)\leq 12\Delta /7+o(\Delta)\), but this improvement has a proof which is more lengthy and does not add significantly to the proof techniques for boundary \(\chi '_{\ell}\).
Reviewer: I.Tomescu

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Bollobás, B., Random graphs, (1985), Academic Press London · Zbl 0567.05042
[2] Bollobás, B.; Harris, A.J., List-colourings of graphs, Graphs and combinatorics, 1, 115-127, (1985) · Zbl 0606.05027
[3] A. Chetwynd and R. Häggkvist, A note on list-colourings, manuscript.
[4] Erdös, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congressus numerantum, 26, 125-157, (1979)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.