On-line list colouring of graphs

Xuding Zhu

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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 ${e\chi(G)-1\over 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 $({e\chi(G)-1\over 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.

Détail

DOI : 10.37236/216

Classification : 05C15