Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On-line list colouring of graphs. | On-line list colouring of graphs Xuding Zhu Department of Applied Mathematics National Sun Yat-sen University Kaohsiung Taiwan 80424 and National Center for Theoretical Sciences Taiwan zhu@ Submitted May 27 2009 Accepted Oct 7 2009 Published Oct 17 2009 Mathematics Subject Classification 05C15 Abstract This paper studies on-line list colouring of graphs. It is proved that the online choice number of a graph G on n vertices is at most x G ln n 1 and the on-line b-choice number of G is at most eXeG1-1 b 1 ln n b. Suppose G is a graph with a given x G -colouring of G. Then for any x G ln n 1 -assignment L of G we give a polynomial time algorithm which constructs an L-colouring of G. For any eXeG1-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 K3 q is on-line 3-choosable if and only if it is 3-choosable but there are graphs of the form K6 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. 1 Introduction Suppose G is a graph f and g are two functions from V G to N we use the convention that N 0 1 2 . with f v g v for all v G V G . An f-assignment of G is a mapping L which assigns to each vertex v of G a set L v of f v positive integers as permissible colours. A g-colouring of G is a mapping S which assigns to each vertex v of G a set S v of g v colours such that for any two adjacent vertices u and v S v 0 S u 0. Given a list assignment L of G an L g -colouring of G is a g-colouring S of G such This research was partially supported by the National Science Council under grant NSC97-2115-M-110-008-MY3 THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R127 1 that for each vertex v S v c L v . We say G is L g -colourable if there exists an L g -colouring of G. We say G is f g -choosable if for every .
