On-line list colouring of graphs (Q2380291)

Summary: This paper studies on-line list colouring of graphs. It is proved that the on-line choice number of a graph \(G\) on \(n\) vertices is at most \(\chi(G)\ln n+1\), and the on-line \(b\)-choice number of \(G\) is at most \(\frac{e_\chi(G)-1}{e-1}(b-1+\ln n)+b\). Suppose \(G\) is a graph with a given \(\chi(G)\)-colouring of \(G\). Then for any \((\chi(G)\ln n+1)\)-assignment \(L\) of \(G\), we give a polynomial time algorithm which constructs an \(L\)-colouring of \(G\). For any \((\frac{e_\chi(G)-1} {e-1}(b-1+\ln n)+b\)-assignment \(L\) of \(G\), we give a polynomial time algorithm which constructs an \((L,b)\)-colouring of \(G\). We then characterize all on-line 2-choosable graphs. It is also proved that a complete bipartite graph of the form \(K_{3,q}\) is on-line 3-choosable if and only if it is 3-choosable, but there are graphs of the form \(K_{6,q}\) which are 3-choosable but not on-line 3-choosable. Some open questions concerning on-line list colouring are posed in the last section.