ON-LINE LIST COLOURING OF RANDOM GRAPHS ALAN FRIEZE.DIETER MITSCHE.XAVIER PEREZ-GIMENEZ.AND PAWEL PRALAT ABSTRACT.In this paper,the on-line list colouring of binomial random graphs(n,p)is studied. We show that the on-line choice number of(n,p)is asymptotically almost surely asymptotic to the chromatic number of 9(n,p),provided that the average degree d=p(n-1)tends to infinity faster than (log logn)/3(logn)2n2/3.For sparser graphs,we are slightly less successful;we show that if d >(logn)2+for some e>0,then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C,where C[2,4],depending on the range of d. Also,for d=O(1),the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number. 1.INTRODUCTION The combinatorial game we study in the paper is played by two players,named Mr.Paint and Mrs.Correct,and is played on a finite,undirected graph in which each vertex has assigned a non-negative number representing the number of erasers at the particular vertex.We assume for simplicity that this number is initially the same for each vertex.In each round,first Mr.Paint selects a subset of the vertices and paints them all the same colour;he cannot use this colour in subsequent rounds.Mrs.Correct then has to erase the colour from some of the vertices in order to prevent adjacent vertices having the same colour.Whenever the colour at a vertex is erased, the number of erasers at that vertex decreases by 1,but naturally,Mrs.Correct cannot erase the colour if she has no erasers left at that vertex.Vertices whose colours have not been erased can be considered as being permanently coloured and can be removed from the game.The game has two possible endings:(i)all vertices have been permanently coloured,in which case Mrs.Correct wins, or(ii)at some point of the game,Mr.Paint presents two adjacent vertices u and v and neither u nor v has any eraser left,in which case Mr.Paint wins.If,regardless of which sets she gets presented, there is a strategy for Mrs.Correct to win the game having initially k-1 erasers at each vertex, we say that the graph is k-paintable.The smallest k for which the graph is k-paintable is called the paintability number of G,and denoted by xp(G).Note that this parameter is indeed well defined:for any graph on n vertices,n-1 erasers at each vertex always guarantee Mrs.Correct to win,as she can always choose one vertex from a set presented to her and erase colours on the remaining ones.This problem is also known as the on-line list colouring and the corresponding graph parameter is also called the on-line choice number of Gsee,for example,[16]and below for the relation to the (off-line)list colouring. Let us recall a classic model of random graphs that we study in this paper.The binomial random graph (n,p)is defined as the probability space (S,F,Pr),where n is the set of all graphs with vertex set {1,2,...,n),F is the family of all subsets of D,and for every Ge, Pr(G)=plE(G)I(1-p)(3)-IE(G)I This space may be viewed as the set of outcomes of (2)independent coin flips,one for each pair (u,v)of vertices,where the probability of success (that is,adding edge uv)is p.Note that p=p(n) may (and usually does)tend to zero as n tends to infinity. The first author is supported in part by NSF Grant CCF0502793. The fourth author is supported in part by NSERC.arXiv:1501.07469v2 [math.CO] 12 May 2015 ON-LINE LIST COLOURING OF RANDOM GRAPHS ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ Abstract. In this paper, the on-line list colouring of binomial random graphs G (n, p) is studied. We show that the on-line choice number of G (n, p) is asymptotically almost surely asymptotic to the chromatic number of G (n, p), provided that the average degree d = p(n − 1) tends to infinity faster than (log log n) 1/3 (log n) 2n 2/3 . For sparser graphs, we are slightly less successful; we show that if d ≥ (log n) 2+ε for some ε > 0, then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C, where C ∈ [2, 4], depending on the range of d. Also, for d = O(1), the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number. 1. Introduction The combinatorial game we study in the paper is played by two players, named Mr. Paint and Mrs. Correct, and is played on a finite, undirected graph in which each vertex has assigned a non-negative number representing the number of erasers at the particular vertex. We assume for simplicity that this number is initially the same for each vertex. In each round, first Mr. Paint selects a subset of the vertices and paints them all the same colour; he cannot use this colour in subsequent rounds. Mrs. Correct then has to erase the colour from some of the vertices in order to prevent adjacent vertices having the same colour. Whenever the colour at a vertex is erased, the number of erasers at that vertex decreases by 1, but naturally, Mrs. Correct cannot erase the colour if she has no erasers left at that vertex. Vertices whose colours have not been erased can be considered as being permanently coloured and can be removed from the game. The game has two possible endings: (i) all vertices have been permanently coloured, in which case Mrs. Correct wins, or (ii) at some point of the game, Mr. Paint presents two adjacent vertices u and v and neither u nor v has any eraser left, in which case Mr. Paint wins. If, regardless of which sets she gets presented, there is a strategy for Mrs. Correct to win the game having initially k − 1 erasers at each vertex, we say that the graph is k-paintable. The smallest k for which the graph is k-paintable is called the paintability number of G, and denoted by χP (G). Note that this parameter is indeed well defined: for any graph on n vertices, n − 1 erasers at each vertex always guarantee Mrs. Correct to win, as she can always choose one vertex from a set presented to her and erase colours on the remaining ones. This problem is also known as the on-line list colouring and the corresponding graph parameter is also called the on-line choice number of G—see, for example, [16] and below for the relation to the (off-line) list colouring. Let us recall a classic model of random graphs that we study in this paper. The binomial random graph G (n, p) is defined as the probability space (Ω, F,Pr), where Ω is the set of all graphs with vertex set {1, 2, . . . , n}, F is the family of all subsets of Ω, and for every G ∈ Ω, Pr(G) = p |E(G)| (1 − p) ( n 2 )−|E(G)| . This space may be viewed as the set of outcomes of ￾ n 2
independent coin flips, one for each pair (u, v) of vertices, where the probability of success (that is, adding edge uv) is p. Note that p = p(n) may (and usually does) tend to zero as n tends to infinity. The first author is supported in part by NSF Grant CCF0502793. The fourth author is supported in part by NSERC. 1