{'fraction_non_alphanumeric': 0.061460908341815716, 'fraction_numerical': 0.01546216858126121, 'mean_word_length': 3.2929671244277987, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Conflict-free coloring of graphs

We study the conflict-free chromatic number chi_{CF} of graphs from extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erd\H{o}s-R\'enyi random graph G(n,p) and give the asymptotics for p=omega(1/n). We also show that for p \geq 1/2 the conflict-free chromatic number differs from the domination number by at most 3.


Introduction and definition
Let G = (V, E) be a simple graph. For every x ∈ V we denote by N (x) = {y ∈ V : xy ∈ E} its neighborhood and by N [x] = N (x)∪{x} its closed neighborhood. A (not necessarily proper) vertex coloring χ of G is called conflict-free, if for each vertex x ∈ V , there exists a vertex y in N [x] whose color is different from the color of each other vertex in N [x]. We then say that y has unique color in N [x]. The conflict-free chromatic number χ CF (G) is the smallest r, such that there exists a conflict-free r-coloring of G. Conflict-free coloring can be interpreted as a relaxation of the usual proper coloring concept where each vertex x is required to have a unique color in its own closed neighborhood N [x]. Hence χ CF (G) ≤ χ(G) for every graph G.
The study of conflict-free colorings was originated in the work of Even et al. [2] and Smorodinsky [7] who were motivated by the problem of frequency assignment in cellular networks. (See the recent survey by Smorodinsky [8].) In most of these classical instances the graphs studied arise from a geometric setting. Recently Pach and Tardos [5] initiated the study of the problem for abstract graphs and hypergraphs. Here we continue the consideration of conflictfree colorings of abstract graphs.
Note that, unlike the proper coloring number, the conflict-free chromatic number is not monotone. In particular, in the two extremes χ CF (K n ) = 2 for the complete graph and χ CF (K n ) = 1 for the empty graph, while the conflictfree chromatic number of general graphs can be arbitrarily high. We investigate this parameter from extremal and probabilistic points of view.
Pach and Tardos [5] raised the problem of determining the order of magnitude of χ CF (n) := max{χ CF (G) : |V (G)| = n}, the largest conflict-free chromatic number an n-vertex graph can have. From above they showed χ CF (n) = O ln 2 n but from below they could only prove that the conflictfree coloring number of the random graph G n, 1 2 is asymptotically almost surely Ω(ln n), hence χ CF (n) = Ω(ln n). Here asymptotically almost surely means probabilities tending to 1 as n goes to infinity and it will be abbreviated below as a.a.s.
At first one could try to improve the lower bound χ CF (n) by considering the random graph G(n, p) with some p = p(n) = 1/2. In our first theorem we give tight estimates (holding a.a.s.) for the conflict-free chromatic number of these random graphs. Our bounds show that some probabilities p(n) → 0 yield the highest conflict-free coloring numbers for the G(n, p(n)), but these are only a constant factor larger than those of G(n, 1/2).
To state our theorem we introduce Notice that the maximum is taken at i = ⌊1/p⌋ so we have and (as simple calculation shows) this is a strictly increasing function tending to e −1 as p goes to 0.
Note that the theorem implies χ CF (G(n, p)) = O(ln n) a.a.s. for all p considered.
For 1/2 ≤ p < 1 we can prove an even tighter result: the conflict-free coloring number differs by at most 3 from the domination number. A set S of vertices of a graph G constitutes a dominating set if each v ∈ V is either in S or is adjacent to a vertex in S. The domination number D(G) is the smallest size of a dominating set in G.
The domination number of the random graph with constant p was pinned down to be one of two integers a.a.s. [9]. Furthermore, it was observed in [3] that the same result holds also for a variable p(n): Theorem 3 ( [9,3]). For 1/2 ≤ p < 1 the domination number D(G(n, p(n)) is either ln n−2 ln ln n+ln ln 1 1−p − ln(1−p) + 1 or one more a.a.s.
Hence the behavior of χ CF is also very well understood in this range. In fact, we prove Theorem 2 by calculating the a.a.s. lower bound on χ CF (G(n, p)) and comparing it with the a.a.s. domination number. Notice that using Theorem 3 Theorem 2 implies Theorem 1 for the range p ≥ 1/2, where we have µ(p) = p. We note that in Theorems 1 and 3 for p < 1 2 the domination number and the conflict-free chromatic number differ in the asymptotics.
In our final result we resolve the open problem of [5] regarding χ CF (n) by constructing n-vertex graphs G with χ CF (G) = Ω(ln 2 n).
The structure of the paper is the following: in Section 2 we prove Theorems 1 and 2, while Theorem 4 is proven in Section 3. For simplicity we routinely omit floor and ceiling signs as long as they don't influence the validity of our asymptotic statements.

Notation
Let G be a graph with vertex set V = V (G) and let A ⊆ V . We say that N (1) We use V m to denote the set of all m-element subsets of V .
2 Evolution of the conflict-free chromatic number in random graphs

Upper bounds
A simple upper bounds is obtained from the fact that any proper coloring is a conflict-free coloring, so χ CF (G) ≤ χ(G).
However, this bound is a.a.s. not tight for the random graph G(n, p) in the range of p we are interested in. Another inequality involves domination. If is a set of vertices S is a dominating set of G then one can construct a conflict-free coloring of G with |S| + 1 colors by giving |S| distinct colors to the vertices in S and one further color to vertices in V (G) \ S. Hence for every graph G This proves the upper bound in Theorem 2.
The rest of this section deals with the upper bound in Theorem 1.
Regarding conflict-free colorings the crucial property of a vertex x is whether it has exactly one neighbor in some color class S and hence the color of S is . For a fixed set S and a fixed vertex x ∈ V \ S the probability of this happening is |S|p(1 − p) |S|−1 . This motivates our definition of µ(p) in Section 1 as the maximum of this probability for any color class size. We let m = ⌊1/p⌋ stand for the "most desirable" color class size maximizing the above probability and giving µ = mp(1 − p) m−1 .
Since the upper bound in Theorem 2 implies the upper bound in Theorem 1 for p ≥ 1 2 , we assume p < 1 2 from now on. To start we prove two technical lemmas for random graphs.
First we give an explicit bound on the probability that the domination number of a random graph is extremely low. We need the explicit bound in because we will use the union bound for more than a constant number of similar events and thus the a.a.s. bound of Theorem 3 is not enough. Lemma 1. For any ℓ ∈ N + and p with 100 ℓ < p < 1 2 we have that where m = ⌊1/p⌋ as before.

Proof
Throughout the proof we will use that m

This is independent for all
We know that the expected size of the one-neighborhood of a set of vertices of size m is (|V | − m)µ. The following is a routine observation that the actual size deviates largely from this expectation with a very low probability.

Proof
For an arbitrary set S ⊂ V of size m and vertex x ∈ V \ S, the probability that x has exactly one neighbor in S is µ. The random variable N (1) (S) is the sum of ℓ − m mutually independent characteristic variables and its expectation is µ(ℓ − m). Hence by the Chernoff bound and the union bound we have and the bound follows if K is sufficiently large.
Let us choose δ = δ(ǫ) > 0 such that it satisfies and assume K = K(δ) from the Lemma 2 satisfies K > 100 so we can also use Lemma 1. Assuming p = p(n) satisfies np → ∞ we give a deterministic algorithm which a.a.s. constructs a conflict-free coloring of G(n, p) using (1 + ǫ) ln(np) − ln(1−µ) colors. In this algorithm d(G i ) denotes the degeneracy of the graph G i , i.e., the largest minimum degree a non-empty subgraph of G i has.
while n i > ln ln n and p > K ni do select an independent set S i by starting with S i = ∅ and iteratively adding the smallest vertex in N Gi Notice that all executions of the main while loop of the algorithm use a separate color and only color 0 is used in many executions. Note also that this color zero is a "filler color" as it is never used as the unique color in the closed neighborhood of some vertex to ensure the conflict-free property of the coloring is obtained.
Recall that the degeneracy d(G i ) of the graph G i and a proper coloring of G i with d(G i ) + 1 colors (as required in the last line of the algorithm) is easy to find efficiently.
Let I be the last value of the index i in the algorithm. Clearly the algorithm colors all vertices with I + d(G I ) + 1 colors. To see that this coloring is conflictfree let w ∈ V (G) be an arbitrary vertex and let i be the largest index with w ∈ V (G i ). If i < I, then there is a unique vertex in N [w] of color i (which may or may not be w itself). If i = I, then w has unique color in N [w].
To finish the proof it is enough to bound the values of I and d(G I ) a.a.s. We start with I. Note that for any 1 ≤ i ≤ I the sets S 1 , . . . , S i−1 selected by the algorithm, and hence the vertex set V (G i ) as well, depend only on the edges incident to S 1 ∪ · · · ∪ S i−1 . Thus, given any way the main while loop is executed for the first i − 1 times, the graph G i is still a random graph G(n i , p). Now we estimate the probability that N (1) . This can happen either with |S i | = m or with |S i | < m. The probability of the former is bounded by Lemma 2, while the latter implies that S i is dominating in G i , the probability of which is bounded by Lemma 1. Using the explicit bounds in the lemmas and the fact that the sizes of the graphs considered are decreasing and lower bounded by a super constant function of n we conclude that a.a.s. in no iteration do we have either of these anomalies: Thus a.a.s. we must have n i+1 ≤ (1 − (1 − δ)µ)n i for each i < I. Using n 1 = n and n I−1 > K/p we have a.a.s.
It remains to show that a.a.s. d(G I ) < δ ln(np) and using the defining inequality (1) for δ the upper bound in Theorem 1 follows. We use again the observation that independent of the executions of the while loop G I is a random graph G(n I , p) with n I being small to trigger the halting condition. If we have p ≤ K/n I , then the expected degree of any vertex in G(n I , p) is less than K. Hence either a.a.s. d(G I ) ≤ K by the results of [6] and [4] and we are done as K < δ ln(np), or n I is bounded by a constant, in which case we can color G I with n I ≤ δ ln(np) colors. If, however, p > K/n I we must have n I ≤ ln ln n to halt the while loop, so we have ln(np) > ln(Kn/n I ) = Ω(ln n). Thus we have d(G I ) < n I < δ ln(np) if n is large enough.
Note that the ln ln n bound in the halting condition of the algorithm can be replaced by any function that tends to infinity and is o(ln n).
Furthermore, observe that if d(G I ) < δ ln(np) (which happens a.a.s.), one can color G I with δ ln(np) colors properly in linear time.

Lower bounds
In [5], Tardos and Pach used the concept of universality to show the lower bound χ CF G n, 1 We introduce a similar concept, which is closer related to the idea of conflict-free coloring. We call a graph G (k, f )-spoiling, if for any k disjoint subsets A 1 , . . . , The vertex x is called a f -spoiler for (A 1 , . . . , A k ) and we say that (A 1 , . . . , A k ) is spoiled by x. We call a graph k-spoiling, if it is (k, f )-spoiling for some f .
The following observation just serves to give an intuition for the concept.
The next lemma is the essence of all lower bounds in Theorem 1.

Proof
Let G be (k, f )-spoiling for some f and consider an arbitrary k-coloring χ of V (G). We need to show that it is not conflict-free. We define subsets A 1 , . . . , A k ⊆ V (G). For each color i which is used less than f times by χ, we define A i to be the whole color class χ −1 ({i}). For each color i which is used on at least f vertices by χ, we set an arbitrary f -subset of vertices with color i to be A i . Since G is (k, f )-spoiling we find a vertex x which is an fspoiler for these sets. Clearly, N [x] has no unique color, showing that χ is not conflict-free.
We first prove the tight lower bound of Theorem 2 via studying the spoilers of G(n, p) for p ≥ 1 2 . Comparing the bound of Theorem 3 of Wieland and Godbole [9] and Glebov, Liebenau, and Szabó [3] with the bound in the following lemma finishes the proof. .

Proof
We show that G(n, p) is a.a.s. (k, 3)-spoiling. Take any set and finally for |A| = 3 we have Then for any family A = {A 1 , . . . , A k } of k sets of size at most f = 3, the probability that a fixed vertex

Thus
Pr A is not spoiled by any There are at most (n + 1) 3k ways A can be selected, so by the union bound we have ln n − 2 ln ln n + ln ln 1 assuming p ≤ 1 − 1 n . Otherwise k = 0 and the statement of the lemma becomes trivial, since every graph is 0-spoiling.
The next lemma provides the lower bound in Theorem 1 when p < 1 2 .

Proof
Similarly to the last section, we fix m = 1 p . We show that G (n, p) is a.a.s. (k, 6m)-spoiling. First we observe that for any fixed S ⊂ V of size at most 6m and a fixed vertex x ∈ V \ S, the probability that x spoils S is at least 1 − µ. Note that 1 − µ is exactly the probability if |S| = m and by the definition of µ as a maximum it is at least this much for other sizes strictly below 6m. A simple way to see the bound for |S| = 6m is to partition S into six parts of size m each. The probability that x has exactly one neighbor in any one of them is µ, these events are independent, so the probability that this holds for at least two of them is exactly 1 − (1 − µ) 6 − 6µ(1 − µ) 5 . Since we have µ > e −1 this is larger than 1 − µ.
Note that k ≤ 3 ln(np) since µ > 1/e. First we fix a family A of k disjoint sets of size at most 6m each and estimate the probability that no vertex x ∈ V \ A is a spoiler for it.
where in the second inequality we use the fact that | A| ≤ 6mk < n/2 for K large enough. The union bound for the probability that this happens for any family A of k sets of size at most 6m each is enough now to finish the proof.

Graphs with large conflict-free chromatic number
In this section we show the existence of n-vertex graphs G with χ CF (G) = Ω(ln 2 n). This gives the correct order of magnitude of χ CF (n) and proves Theorem 4.
To show the statement, we construct an n-vertex graph G with random methods. The vertex set is partitioned into classes L 1 , . . . , L k of size n k each, with k = ⌊ln n⌋. The edges will be selected at random, independently of each other. To define the probabilities we let the weight of a vertex x ∈ L i be The probability of an edge between vertices x ∈ L i and y ∈ L j is equal to The weight of a set S ⊆ V is defined to be the sum of the weights of its elements, For a vertex coloring χ we say that vertex v takes care of itself if the color of v is unique in N [v], i.e. every u ∈ N (v) has a color different from χ(v). We say that a color class S takes care of a vertex x if x ∈ N (1) (S). The crucial probability, denoted by p(x, S), that a vertex x ∈ L i is taken care of by a color class S not containing x is equal to Note that since the function ze −z has a unique maximum at z = 1, we always have p(x, S) < e −0.01 . If χ is a conflict-free coloring, then every vertex is taken care of either by itself or by a color class not containing this vertex.
We call a set heavy if its weight is larger than √ n, otherwise we call it light. Note that since any vertex has weight at least 0.99 ln n ≥ n −0.02 , we obtain for any light color class S |S| ≤ w(S)n 0.02 ≤ n 0.52 .
In the following lemma we list three properties, which hold a.a.s for our random G and, together, imply that no conflict-free coloring exists with o ln 2 n colors. As usual, α(G) denotes the independence number of G, i.e. the size of a largest independent set. Lemma 6. For G the following three properties hold a.a.s.

Proof
Since the probability for each pair of vertices to be an edge of G is at least 0, 99 2 ln n , the largest independent set is at most as large as it is in G(n, 0, 99 2 ln n ), that is, a.a.s. at most 2 ln(0,99 2 ln n n) 0,99 2 ln n < n 0.6 for large n (see, for example, [1]).
For the second statement fix a subset S ⊆ V with weight at least n 0.5 and a set A ⊆ V \ S with at least n 0.6 elements. We estimate the probability that all elements x ∈ A are in the one-neighborhood of S. (Here we used that w x w(S) ≥ 0.99 ln n n 0.5 > n 0.48 and that ze −z is decreasing in the interval [1, ∞).) Summing up over all the at most 2 n · 2 n choices of S and A we obtain that the probability that (ii) fails tends to 0.
For the third part fix subsets S 1 , . . . , S r with w(S i ) ≤ √ n and B with |B| = n 0.7 . We estimate the probability that all x ∈ V \ B are in the oneneighborhood of at least one of the S i . For this we first show that r i=1 p(x, S i ) > 0.01 ln n for at most half of the vertices x ∈ V . Indeed, otherwise ≤ r (100e + 100 + 200) n ln n , a contradiction. For the last estimate we used that for a fixed color class S i , where z j is a geometric progression with quotient 0.99. The terms of the sum for z j ≤ 1 can be estimated by ez j and hence this part is at most e 1−0.99 = 100e. The sum of the terms for z j ≥ 2 can be estimated by 100 ∞ 1 ze −z+1 dz = 200. And finally the sum of the terms for 1 < z j < 2 can be estimated by 100, since there are at most 100 such z j 's, and for each of them the value of the function is at most 1.
Let V ′ ⊆ V be the set of those vertices x ∈ V for which r i=1 p(x, S i ) ≤ 0.01 ln n. Then by the above |V ′ | ≥ n/2. Here we used that in the range of our interest, i.e. for 0 < z = p(x, S i ) < e −0.01 , we have 1 − z > e −5z . The sets S 1 , . . . S r and B with the given properties can be chosen at most n n 0.7 (n + 1) ways, where we first choose a set B of size n 0.7 from V , and then choose one by one the vertices forming the sets S 1 , . . . , S r . Hence with probability tending to 1 the third condition holds.
Finally, we show how the above properties imply the existence of graphs without a conflict-free coloring with 10 −5 ln 2 n colors.
Proof of Theorem 4. Let us take a graph G having properties (i) − (iii) of Lemma 6 with a sufficiently large vertex set. Take an arbitrary r-coloring χ of G, where r = 10 −5 ln 2 n as in the lemma. We prove that χ is not a conflict-free coloring. Let T, H, and L ⊆ V be the subset of vertices that take care of themselves, are taken care of by a heavy color class, and are taken care of by light color classes, respectively. If χ were a conflict-free coloring, then Vertices taking care of themselves. A set of vertices that take care of themselves and have the same color must form an independent set in G. Hence by (i) any color class can contain at most n 0.6 vertices that take care of themselves. So |T | ≤ rn 0.6 .
Vertices taken care of by heavy color classes. Fix a heavy color class S. By (ii) at most n 0.6 vertices are taken care of by S. Hence |H| ≤ rn 0.6 .
Vertices taken care of by light color classes. Let S 1 , . . . , S r be the light color classes of χ. Let B = T ∪ H. Then |B| ≤ 3rn 0.6 < n 0.7 for sufficiently large n. By (iii) there will be a vertex x ∈ V \ B which is not taken care of by any of the S i . Since x ∈ B, x does not take care of itself and it is not taken care of by a heavy color class either. This concludes the proof that χ is not a conflict-free coloring.

Remarks and open problems
At the two extreme of p the trivial upper bounds given by the chromatic number and the domination number plus one are tight. For the very sparse range of p = o(1/n) the random graph G(n, p) is a.a.s. a tree, hence both χ(G(n, p)) and χ CF (G(n, p)) are a.a.s. 2. On the other end for p ≥ 1 2 we showed that |χ CF − D| ≤ 3. The particular questions remain to answer: -In what range is χ CF (G(n, p)) = D(G(n, p)) + 1 a.a.s.? -In what range χ(G(n, p)) = χ CF (G(n, p)) a.a.s.? In particular we would be interested in where the threshold of 3-conflict-free colorability is and how much it is different, if at all, from the threshold of 3-colorability.
-Does χ CF (G(n, p)) behave in a unimodal way? For example one might consider the median function and ask whether it is unimodal.
It is an interesting general question to characterize those graphs where equality holds for χ CF (G) = χ(G) or χ CF (G) = D(G) + 1.
By [9] and [3] we have the concentration of χ CF (G(n, p)) on two values a.a.s. whenever χ CF (G(n, p)