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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Game colouring directed graphs. | Game colouring directed graphs Daqing Yang Center for Discrete Mathematics Fuzhou University Fuzhou Fujian 350002 China daqing85@ Xuding ZW National Sun Yat-sen University and National Center for Theoretical Sciences Taiwan zhu@ Submitted Feb 6 2009 Accepted Dec 29 2009 Published Jan 5 2010 Mathematics Subject Classification 05C15 05C20 05C57 Key words and phrases dichromatic number digraph colouring game directed graph marking game planar graph. Abstract In this paper a colouring game and two versions of marking games the weak and the strong on digraphs are studied. We introduce the weak game chromatic number xwg D and the weak game colouring number wgcol D of digraphs D. It is proved that if D is an oriented planar graph then xwg D wgcol D 9 and if D is an oriented outerplanar graph then xwg D wgcol D 4. Then we study the strong game colouring number sgcol D which was first introduced by Andres as game colouring number of digraphs D. It is proved that if D is an oriented planar graph then sgcol D 16. The asymmetric versions of the colouring and marking games of digraphs are also studied. Upper and lower bounds of related parameters for various classes of digraphs are obtained. 1 Introduction The game chromatic number of graphs was first introduced by Brams for planar graphs published by Gardner 9 and then reinvented for arbitrary graphs by Bodlaender in 4 . Supported in part by NSFC under grants 10771035 and 10931003 grant SX2006-42 of colleges of Fujian. iGrant number NSC95-2115-M-110-013-MY3. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R11 1 Given an undirected graph G and a set X of colours. Two players Alice and Bob take turns with Alice having the first move to colour the vertices of G with colours from X. At the start of the game all vertices are uncoloured. A play by either player colours an uncoloured vertex with a colour from X so that no two adjacent vertices receive the same colour. Alice wins if eventually the whole graph
