Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Game list colouring of graphs. | Game list colouring of graphs M. Borowiecki Faculty of Mathematics Computer Science and Econometrics University of Zielona Góra Szafrana 4a 65-516 Zielona Góra Poland E. Sidorowicz Faculty of Mathematics Computer Science and Econometrics University of Zielona Góra Szafrana 4a 65-516 Zielona Góra Poland Zs. Tuza Computer and Automation Institute Hungarian Academy of Sciences Hungary and Departament of Computer Science Unversity of Pannonia Veszprem Hungary tuza@ Submitted Jan 11 2006 Accepted Mar 15 2007 Published Mar 22 2007 Mathematics Subject Classifications 05C15 05C75 Abstract We consider the two-player game defined as follows. Let G L be a graph G with a list assignment L on its vertices. The two players Alice and Bob play alternately on G Alice having the first move. Alice s goal is to provide an L-colouring of G and Bob s goal is to prevent her from doing so. A move consists in choosing an uncoloured vertex v and assigning it a colour from the set L v . Adjacent vertices of the same colour must not occur. This game will be called game list colouring. The game choice number of G denoted by chg G is defined as the least k such that Alice has a winning strategy for any k-list assignment of G. We characterize the class of graphs with chg G 2 and determine the game choice number for some classes of graphs. Research supported in part by the Hungarian Scientific Research Fund grant OTKA T-049613. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R26 1 1 Introduction and notation All graphs considered in this paper are simple . finite undirected loopless and without multiple edges. The notation H G H c G means that H is an induced subgraph of G. We say that G contains H whenever G contains an induced subgraph isomorphic to H. The set of neighbours of a vertex v 2 V G is denoted by NG v or briefly by N v . The degree of v is the number N v I and is denoted by d v . The symbol A G denotes the .
