A new upper bound for the list chromatic number (Q1121274): Difference between revisions

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}\).