A note on vertex list colouring (Q2757076)

Suppose that we are given a graph \(G\), and for each vertex \(v\) of \(G\) we are given a list set \(S(v)\) of \(k\) colours. A list-colouring is a selection of a colour from \(S(v)\) for each vertex \(v\) such that adjacent vertices receive distinct colours. \textit{B. Reed} [The list colouring constants, J. Graph Theory 31, No. 2, 149-153 (1999; Zbl 0926.05019)] conjectured that a list-colouring always existed provided that for each vertex \(v\) and each colour \(c\), the number of neighbours of \(v\) that have colour \(c\) in their lists is at most \(k-1\). In this paper the author proves a weak version of Reed's conjecture; namely the case that \(k\) is even and the number of neighbours of \(v\) that have colour \(c\) in their lists is at most \(k/2\).