Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Game colouring directed graphs"

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@yahoo.com Xuding ZW National Sun Yat-sen University and National Center for Theoretical Sciences Taiwan zhu@math.nsysu.edu.tw 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