Introduction
A central problem both in discrete math and in theoretical computer science, graph coloring , is to color each vertex of a given graph G = ( V , E ) G=(V,E) G = ( V , E ) with as few colors as possible so that no two adjacent vertices have the same color. We study the online coloring problem, the online version of graph coloring, in which the vertices are given one by one (together with their incident edges). Immediately after a vertex arrives, we must assign it a color before the next vertex arrives. Once the color is assigned, it cannot be changed. Online coloring is one of the most central questions in online algorithms, alongside online matching, k k k -server, and the list update problem [3 ] .
Historical Background
Historically, the central focus in the study of online algorithms has been competitive analysis , which compares an online algorithm’s performance to that of an optimal offline algorithm. This is also the case in online coloring; the competitive ratio1 for online coloring was studied as early as the 1980s [14 , 25 ] . However, straightforward algorithms perform poorly. For example, the First-Fit algorithm, which always chooses the smallest available color, has a competitive ratio of at least n / 4 n/4 n /4 (for graphs with n n n vertices), as it may use n / 2 n/2 n /2 colors even on a bipartite graph (Figure 1 ). This makes online coloring particularly challenging compared to other online problems.
Figure 1. A worst-case bipartite graph on which First-Fit uses n / 2 n/2 n /2 colors.
Competitive ratio. As one of the most important results in online coloring, Halldórsson and Szegedy [17 ] [17 ] presented a lower bound of Ω ( n / log 2 n ) \Omega(n/\log^2 n) Ω ( n / log 2 n ) on the competitive ratio. This shows the inherent difficulty of online coloring. However, a central question remains: “Do randomized algorithms outperform deterministic algorithms in online coloring? ”
Deterministic vs. randomized. On the deterministic side, Lovász, Saks, and Trotter [25 ] [25 ] found an algorithm with a competitive ratio of O ( n / log ∗ n ) O(n/\log^* n) O ( n / log ∗ n ) , followed by improvements to O ( n log log log n / log log n ) O(n\log\log\log n/\log\log n) O ( n log log log n / log log n ) by Kierstead (1998) [21 ] and to O ( n / log log n ) O(n/\log\log n) O ( n / log log n ) by Kawarabayashi, Yoneda, and Yoneda in 2025 [23 ] (to appear in SODA ’27). On the randomized side, Vishwanathan [29 ] [29 ] found an algorithm with a competitive ratio of O ( n / log 1 / 2 n ) O(n/\log^{1/2} n) O ( n / log 1/2 n ) , and improved to O ( n / log n ) O(n/\log n) O ( n / log n ) by Halldórsson [16 ] [16 ] . We assume an oblivious adversary for randomized algorithms, where the input is fixed independently of the algorithm’s output.
Although the best-known randomized upper bound is better than the deterministic one, the asymptotic separation between the optimal competitive ratios remains open because the best-known lower bounds for both are Ω ( n / log 2 n ) \Omega(n/\log^{2} n) Ω ( n / log 2 n ) ; see Figure 2 . Whether an asymptotic separation exists is crucial not only for online coloring but also for the broader field of online algorithms. In the worst-case analysis of deterministic algorithms, we must assume an “adversarial attack”, which has also been studied in the context of machine learning, such as in the adversarial bandit problem [1 ] . Therefore, settling the existence question would clarify whether the adversary is effective. Note that an asymptotic separation has been established for many online problems, such as online caching [12 ] and the k k k -server problem in general metric spaces [26 , 6 , 27 ] .
Figure 2. The previously known lower and upper bounds for randomized and deterministic algorithms. These bounds do not establish an asymptotic separation.
Positioning. Online coloring has a deep connection with structural graph theory in general, as many algorithmic improvements are made by exploiting novel subgraph structures [29 , 23 BFS+26, 30 ] . This problem has also been studied in the context of informational hardness [15 , 5 ] and parallel and distributed computing [16 AEL+23] . Moreover, online coloring can be applied to scheduling [11 ] , resource allocation [19 ] , and cloud computing [28 ] .
Related work. In online coloring, researchers have studied a wide range of topics beyond the competitive ratio. The first topic is online coloring for k k k -colorable graphs (for a constant k ≥ 2 k \ge2 k ≥ 2 ). On the deterministic side, Kierstead [21 ] presented an algorithm that uses O ~ ( n 1 − 1 / k ! ) \widetilde{O}(n^{1-1/k!}) O ( n 1 − 1/ k ! ) colors, and recently Kawarabayashi, Yoneda, and Yoneda [23 ] improved the bound to O ~ ( n 1 − 2 / ( k ( k − 1 ) ) ) \widetilde{O}(n^{1-2/(k(k-1))}) O ( n 1 − 2/ ( k ( k − 1 )) ) colors. On the randomized side, Vishwanathan [29 ] found an algorithm that uses O ~ ( n 1 − 1 / ( k − 1 ) ) \widetilde{O}(n^{1-1/(k-1)}) O ( n 1 − 1/ ( k − 1 ) ) colors. A large gap remains to the best-known lower bound of Ω ( log k − 1 n ) \Omega(\log^{k-1} n) Ω ( log k − 1 n ) colors [29 ] .2
The second topic is online coloring for special graph classes. Kierstead and Trotter [22 ] presented a 3-competitive online coloring algorithm for interval graphs. Trees [7 , 14 ] , bipartite graphs [25 , 5 , 13 ] , planar graphs [18 ] , and bounded-treewidth graphs [4 ] can be colored online using Θ ( log n ) \Theta(\log n) Θ ( log n ) colors. For every fixed ε > 0 \varepsilon> 0 ε > 0 , an O ( n ε ) O(n^{\varepsilon}) O ( n ε ) -color algorithm exists for graphs with sufficiently large odd girth [30 ] . First-Fit performs well on d d d -degenerate graphs; it uses only O ( d log n ) O(d\log n) O ( d log n ) colors. For more results, see the survey by Kierstead [20 ] .
A related, recently well-studied topic is online edge coloring , in which we must color edges that arrive one by one. Edge coloring is easier than vertex coloring: a ( 1 + o ( 1 ) ) (1+o(1)) ( 1 + o ( 1 )) -competitive algorithm is known for graphs with maximum degree Δ = ω ( log n ) \Delta= \omega(\log n) Δ = ω ( log n ) [9 BSV+25] .
Our Contributions
In this paper, we improve the bounds on competitive ratios from three sides, as stated below.
Theorem 1.1. Every deterministic online coloring algorithm is Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) -competitive.
Theorem 1.2. There exists a polynomial-time randomized online coloring algorithm, against an oblivious adversary, that attains a competitive ratio of O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) .
Theorem 1.3. For every fixed ε > 0 \varepsilon> 0 ε > 0 , there exists a polynomial-time deterministic online coloring algorithm that attains a competitive ratio of O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) .
These results represent the first substantial improvements since the 20th century. Theorem 1.1 improves on Halldórsson and Szegedy [17 ] [17 ] . Theorem 1.2 improves on Halldórsson [16 ] [16 ] . Theorem 1.3 is the first poly( log log n ) (\log\log n) ( log log n ) -factor improvement since Kierstead (1998) [21 ] . See Figure 3 for a comparison. Consequently, the gap between the upper and lower bounds for the randomized case is almost closed; only a factor of O ( ( log log n ) 2 ) O((\log\log n)^2) O (( log log n ) 2 ) remains.
Figure 3. Historical improvements in the upper and lower bounds for randomized (left) and deterministic (right) algorithms.
Importantly, Theorems 1.1 and 1.2 show that randomization gives an asymptotic advantage in online graph coloring. Every deterministic algorithm has worst-case competitive ratio Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) , whereas our randomized algorithm achieves expected competitive ratio o ( n / log n ) o(n/\log n) o ( n / log n ) against an oblivious adversary. The distinction is visible even on graphs that can be colored offline with O ( log n ) O(\log n) O ( log n ) colors. For every deterministic algorithm, there is an input where no color is used more than twice, forcing the algorithm to use at least n / 2 n/2 n /2 colors. In contrast, on every fixed input in this class, our randomized algorithm uses o ( n ) o(n) o ( n ) colors in expectation.
In addition, to obtain Theorem 1.3, we develop a better deterministic online coloring algorithm for graphs without r r r -cliques: our algorithm uses O ( n ( log log n / log n ) 1 / ( r − 2 ) ) O(n(\log\log n/\log n)^{1/(r-2)}) O ( n ( log log n / log n ) 1/ ( r − 2 ) ) colors for every constant r ≥ 3 r \ge3 r ≥ 3 (Remark 6.7 ). The best previously known deterministic algorithm by Bradač et al. [8 ] [BFS+26] uses O ( n log ( r − 1 ) n / log ( r − 2 ) n ) O(n\log^{(r-1)}n/\log^{(r-2)}n) O ( n log ( r − 1 ) n / log ( r − 2 ) n ) colors, where log ( j ) n \log^{(j)}n log ( j ) n denotes the j j j -fold iterated logarithm.
Improvements on Larger Chromatic Numbers
Beyond the competitive analysis, our results also improve performance and hardness for online coloring of graphs with larger chromatic numbers by a significant margin.
Historically, competitive analysis in online coloring has focused on improving algorithmic performance on graphs with small chromatic numbers, particularly k k k -colorable graphs for a constant k ≥ 3 k \ge3 k ≥ 3 . For the randomized side, an O ~ ( n 1 − 1 / ( k − 1 ) ) \tilde{O}(n^{1-1/(k-1)}) O ~ ( n 1 − 1/ ( k − 1 ) ) -color algorithm [16 ] yielded an O ( n / log n ) O(n/\log n) O ( n / log n ) -competitive algorithm. For the deterministic side, an O ~ ( 2 2 k + 3 n 1 − 2 / ( k ( k − 1 ) ) ) \tilde{O}(2^{2^{k+3}}n^{1-2/(k(k-1))}) O ~ ( 2 2 k + 3 n 1 − 2/ ( k ( k − 1 )) ) -color algorithm [23 ] yielded an O ( n / log log n ) O(n/\log\log n) O ( n / log log n ) -competitive algorithm. However, we take the opposite approach, targeting graphs with large and middle-tier chromatic numbers.
Large-Chromatic Approach (Theorem 1.1 and Theorem 1.2)
In Theorem 1.1 and Theorem 1.2 , we consider online coloring of graphs with a large chromatic number k k k , for example, when k = n c k=n^c k = n c for some c > 0 c>0 c > 0 . To start, consider Algorithm 1, which uses each color on at most two vertices and, whenever possible, uses a color already used exactly once. This algorithm is somewhat effective when k k k is large; when k = o ( n ) k=o(n) k = o ( n ) , it uses only n / 2 + o ( n ) n/2+o(n) n /2 + o ( n ) colors, and only an o ( 1 ) o(1) o ( 1 ) fraction of the colors appear on exactly one vertex.
Proposition 1.4. Let n , k ≥ 1 n,k\ge1 n , k ≥ 1 be integers. For a n n n -vertex graph without ( k + 1 ) (k+1) ( k + 1 ) -cliques, Algorithm 1 uses at most n + k 2 \frac{n+k}{2} 2 n + k colors. Also, the same bound trivially holds for k k k -colorable graphs.
Proof. Let v 1 , … , v t v_1,\ldots,v_t v 1 , … , v t be the vertices whose colors are used exactly once. These vertices must form a clique, because if v i v_i v i and v j v_j v j are not adjacent for some i , j i,j i , j (i < j i<j i < j ), then v j v_j v j would have been colored with the same color as v i v_i v i , a contradiction. Hence, t ≤ k t\le k t ≤ k by assumption. Since all other colors are used exactly twice, the algorithm uses t + n − t 2 = n + t 2 ≤ n + k 2 t+\frac{n-t}{2}=\frac{n+t}{2}\le\frac{n+k}{2} t + 2 n − t = 2 n + t ≤ 2 n + k colors. □
Since Algorithm 1, which uses at most two vertices per color, performs well for large chromatic numbers k k k , a natural question arises: “Can this approach be extended to three vertices per color?” The answer is no for deterministic algorithms but yes for randomized algorithms.
For every deterministic algorithm, there exists an Θ ( log n ) \Theta(\log n) Θ ( log n ) -colorable graph on which the algorithm uses each color on at most two vertices and hence uses at least n / 2 n/2 n /2 colors, as we will prove in § 4 . This is how we derive an Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) lower bound.
In contrast, for randomized algorithms, our new algorithm colors any k k k -colorable graph with expected n / 3 + o ( n ) n/3+o(n) n /3 + o ( n ) colors when k = o ( n 1 / 2 ) k=o(n^{1/2}) k = o ( n 1/2 ) , as we prove in Subsection 5.3. In general, for every integer t ≥ 2 t\ge2 t ≥ 2 , there exists a randomized algorithm that colors any k k k -colorable graph with expected n / t + o ( n ) n/t+o(n) n / t + o ( n ) colors when k = o ( n 1 / ( t − 1 ) ) k=o(n^{1/(t-1)}) k = o ( n 1/ ( t − 1 ) ) . Figure 4 (left) shows the performance by the chromatic
Figure 4. Performance frontiers for online coloring by chromatic number k k k , for randomized and deterministic algorithms. The previous results are shown in blue, and our results are shown in red.
Algorithm 1 An algorithm for online coloring.
1: for each arrival of a vertex v do
2: if there exists a color c that is used exactly once and is not adjacent to v then
3: Color v with color c
4: else
5: Color v with a new color
number k k k . Roughly speaking, the frontier of Halldórsson’s algorithm [16 ] is t k − 1 ≈ n t^{k-1} \approx n t k − 1 ≈ n , while the frontier of our algorithm is k t − 1 ≈ n k^{t-1} \approx n k t − 1 ≈ n , crossing at k = t = Θ ( log n / log log n ) k=t=\Theta(\log n/\log\log n) k = t = Θ ( log n / log log n ) . This is why combining them attains a competitive ratio of O ( n ( log log n / log n ) 2 ) O(n(\log\log n/\log n)^2) O ( n ( log log n / log n ) 2 ) .
Mid-Chromatic Approach (Theorem 1.3)
To improve deterministic algorithms (Theorem 1.3), we cannot take the large-chromatic approach due to the negative lower-bound result. Instead, we take a different approach that focuses on a regime of “moderate” chromatic numbers k k k ; see Figure 4 (right). For background, Kawarabayashi, Yoneda, and Yoneda’s deterministic algorithm [23 ] uses Ω ( ( log log n ) 1 − ε / 2 ) \Omega((\log\log n)^{1-\varepsilon/2}) Ω (( log log n ) 1 − ε /2 ) vertices per color3 in the regime of k ∈ [ 1 , ( log log n ) 1 − ε / 2 ] k \in[1,(\log\log n)^{1-\varepsilon/2}] k ∈ [ 1 , ( log log n ) 1 − ε /2 ] .
In this paper, we also achieve equivalent performance for k ∈ [ ( log log n ) 1 − ε / 2 , ( log log n ) 2 − ε ] k \in[(\log\log n)^{1-\varepsilon/2},(\log\log n)^{2-\varepsilon}] k ∈ [( log log n ) 1 − ε /2 , ( log log n ) 2 − ε ] . We make this possible by upgrading their algorithm with our new technical framework based on clique-free graphs; this is the main technical contribution of this paper. Using this approach, we attain a competitive ratio of O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) .
Organization
Section 2 presents technical overviews of each algorithm. Section 3 presents formal definitions and fundamental lemmas used in our proofs. Section 4 presents an Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) lower bound for the competitive ratio of deterministic online coloring (Theorem 1.1). Section 5 presents an O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) -competitive algorithm for randomized online coloring (Theorem 1.2 ). Section 6 presents an O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) -competitive algorithm for deterministic online coloring (Theorem 1.3). Finally, Section 7 concludes the paper with conjectures.
Technical Overview
Theorem 1.1: The Lower Bound for Deterministic Algorithms
In the worst-case analysis of deterministic online algorithms, we can assume that an adversary determines the neighbors of each new vertex v v v based on the algorithm’s current output. To this end, we develop a strategy for the adversary that forces every (online) color to be used on at most two vertices. For a 2 ℓ 2\ell 2 ℓ -colorable graph (ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 ), we achieve this goal through 2 ℓ 2^\ell 2 ℓ vertices.
Transparent model. Halldórsson and Szegedy [17 ] proved an Ω ( n / log 2 n ) \Omega(n/\log^2 n) Ω ( n / log 2 n ) lower bound based on the transparent model , in which the adversary maintains a (proper) 2 ℓ 2\ell 2 ℓ -coloring φ : V → { 1 , … , 2 ℓ } \varphi: V \to\{1,\ldots,2\ell\} φ : V → { 1 , … , 2 ℓ } in real time. Immediately after the algorithm colors a vertex v v v , the adversary must irrevocably assign φ ( v ) ∈ { 1 , … , 2 ℓ } \varphi(v) \in\{1,\ldots,2\ell\} φ ( v ) ∈ { 1 , … , 2 ℓ } , called a base color (to distinguish it from the “colors” that the algorithm assigns). We assume that the coloring φ \varphi φ is visible to the algorithm. While this model simplifies the analysis, the adversary cannot force every (online) color to appear on at most two vertices for more than 4 ℓ 2 + 2 ℓ 4\ell^2 + 2\ell 4 ℓ 2 + 2 ℓ vertices (Subsection 4.1).
New adversary. We modify the transparent model as follows. For the first vertex v 1 v_1 v 1 of a color, the adversary does not assign the base color φ ( v 1 ) \varphi(v_1) φ ( v 1 ) . For the second vertex v 2 v_2 v 2 of this color, they must assign the base colors φ ( v 1 ) \varphi(v_1) φ ( v 1 ) and φ ( v 2 ) \varphi(v_2) φ ( v 2 ) simultaneously. Here, we impose one rule: the adversary must assign the base color 2 i − 1 2i-1 2 i − 1 to one of them and 2 i 2i 2 i to the other, for some i ∈ { 1 , … , ℓ } i \in\{1,\ldots,\ell\} i ∈ { 1 , … , ℓ } .
When the adversary decides the neighbors of each vertex v v v , they choose a set X v ⊆ { 1 , … , 2 ℓ } X_v \subseteq\{1,\ldots,2\ell\} X v ⊆ { 1 , … , 2 ℓ } such that exactly one of 2 i − 1 2i-1 2 i − 1 and 2 i 2i 2 i belongs to X v X_v X v for each i ∈ { 1 , … , ℓ } i \in\{1,\ldots,\ell\} i ∈ { 1 , … , ℓ } , and draws edges from v v v to all present vertices with a base color not in X v X_v X v . Note that there are 2 ℓ 2^\ell 2 ℓ possible sets. Then, v v v cannot become the “third vertex” of any color (see Figure 5 ). The problem is whether the base colors φ ( v 1 ) \varphi(v_1) φ ( v 1 ) and φ ( v 2 ) \varphi(v_2) φ ( v 2 ) can be validly assigned. The trick is that, as long as the sets X v X_v X v (v ∈ V v \in V v ∈ V ) are all distinct, the adversary can always assign valid base colors. Hence, the adversary can maintain the strategy for 2 ℓ 2^\ell 2 ℓ vertices. This yields an Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) -competitive lower bound.
Figure 5. An example of the neighbor decision by the adversary when X v = { 1 , 4 } X_v = \{1,4\} X v = { 1 , 4 } is selected. The player cannot color v v v with colors 1, 3, or 4, so v v v cannot become the “third vertex”.
Theorem 1.2: The Upper Bound for Randomized Algorithms
We extend Algorithm 1 to “three vertices per color” using randomization. For convenience, we call a color used on exactly ℓ \ell ℓ vertices a “level-ℓ \ell ℓ color”. Given a parameter θ ≥ 1 \theta\ge1 θ ≥ 1 , consider the following
three-layer algorithm: when each vertex v ∈ V v \in V v ∈ V arrives, (1) if v v v can be colored with a level-2 color, use that color, (2) otherwise, if v v v can be colored with at least θ \theta θ level-1 colors, randomly choose one of them, (3) otherwise, use a fresh color. See Figure 6 for an illustration of the algorithm.
Figure 6. A sketch of our algorithm. Each bin represents the set of vertices assigned the same online color. We highlight the colors available to a new vertex v v v (i.e., colors not used by its neighbors).
Analysis. We analyze the expected number of colors used for a k k k -colorable graph. It is easy to see that there are at most k θ k\theta k θ level-1 colors (Lemma 5.1 ). We then analyze the expected number of level-2 colors. To this end, we bound the probability that the final number of level-2 colors is exactly m m m . Consider the scenario in which the vertices with level-2 colors are listed as
( a 1 , b 1 ) , … , ( a m , b m ) ( a 1 < b 1 , … , a m < b m ; b 1 < ⋯ < b m ) , (a_1,b_1),\ldots,(a_m,b_m)\quad(a_1 < b_1,\ldots,a_m < b_m; b_1 < \cdots< b_m), ( a 1 , b 1 ) , … , ( a m , b m ) ( a 1 < b 1 , … , a m < b m ; b 1 < ⋯ < b m ) ,
where a i a_i a i and b i b_i b i have the same color for each i ∈ { 1 , … , m } i \in\{1,\ldots,m\} i ∈ { 1 , … , m } . Here, x < y x < y x < y means that vertex x x x arrives earlier than y y y . This exact scenario happens with probability at most 1 / θ m 1/\theta^m 1/ θ m (Lemma 5.2 ), because when each vertex b i b_i b i arrives, the algorithm must choose the same color as vertex a i a_i a i , which happens with probability at most 1 / θ 1/\theta 1/ θ due to step (2) of the algorithm. On the other hand, the number of lists ( a 1 , b 1 ) , … , ( a m , b m ) (a_1,b_1),\ldots,(a_m,b_m) ( a 1 , b 1 ) , … , ( a m , b m ) that occur with non-zero probability can be shown to be at most k m ( n m ) 2 k^m\binom{n}{m}^2 k m ( m n ) 2 (Lemma 5.3 ). Thus, the probability that there are exactly m m m level-2 colors is at most
1 θ m ⋅ { k m ⋅ ( n m ) 2 } ≤ ( e 2 k n 2 θ m 2 ) m . \frac{1}{\theta^m}\cdot\left\{k^m\cdot\binom{n}{m}^2\right\}\leq\left(\frac{e^2kn^2}{\theta m^2}\right)^m. θ m 1 ⋅ { k m ⋅ ( m n ) 2 } ≤ ( θ m 2 e 2 k n 2 ) m .
This bound rapidly approaches zero beyond m = e n k / θ m = en\sqrt{k/\theta} m = e n k / θ . Hence, the expected number of level-2 colors is O ( n k / θ ) O(n\sqrt{k/\theta}) O ( n k / θ ) (Lemma 5.4 ). As a result, when k = o ( n ) k=o(\sqrt{n}) k = o ( n ) , only an o ( 1 ) o(1) o ( 1 ) fraction of colors are at levels 1 or 2 with parameter θ = n \theta=\sqrt{n} θ = n . In this case, we use n / 3 + o ( n ) n/3+o(n) n /3 + o ( n ) colors in expectation.
Generalization. We further generalize the algorithm to general d ≥ 3 d\geq3 d ≥ 3 layers. With an appropriate parameter setting that uses a different θ \theta θ for each layer, we use n / d + o ( n ) n/d+o(n) n / d + o ( n ) colors in expectation when k = o ( n 1 / ( d − 1 ) ) k=o(n^{1/(d-1)}) k = o ( n 1/ ( d − 1 ) ) , for any fixed d d d . This result leads to an O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) -competitive algorithm by combining with Halldórsson’s algorithm [16 ] ; see also the discussion in Subsection 1.3.
Theorem 1.3: The Upper Bound for Deterministic Algorithms
We present an O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) -competitive deterministic algorithm. Let m : = ( log log n ) 1 − ε / 2 m := (\log\log n)^{1-\varepsilon/2} m := ( log log n ) 1 − ε /2 . Kawarabayashi, Yoneda, and Yoneda’s algorithm [KY27] colors m m m -colorable graphs online using O ( n / m 2 ) O(n/m^2) O ( n / m 2 ) colors. Our goal is to upgrade their algorithm to color m 2 m^2 m 2 -colorable graphs using O ( n / m ) O(n/m) O ( n / m ) colors; this suffices to show the competitive ratio. We clarify the issues that arise in the m 2 m^2 m 2 -colorable case in their algorithm, then present our new technical framework to resolve them.
The KYY27 Framework and its Limitation
First, we describe an algorithm to color 3-colorable graphs using O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors for a small c > 0 c > 0 c > 0 [21 ] . We color each vertex v v v using First-Fit if it can be colored with one of the first n 1 − c n^{1-c} n 1 − c colors. If v v v cannot be colored in this way, then observe that v v v has degree at least n 1 − c n^{1-c} n 1 − c . We color these remaining vertices by exploiting their large degrees, as follows.
Let S S S be the set of vertices colored by First-Fit. For a fixed x ∈ V ∖ S x \in V \setminus S x ∈ V ∖ S , let L 1 : = N S ( x ) L_1 := N_S(x) L 1 := N S ( x ) . Then, in some 3-coloring of G G G , at most 2 colors appear in L 1 L_1 L 1 (Figure 7 , left).
Figure 7. A sketch of an algorithm that colors 3-colorable graphs using O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors.
In addition, for a fixed edge { y , z } \{y, z\} { y , z } with y , z ∈ V ∖ S y, z \in V \setminus S y , z ∈ V ∖ S , let L 2 , y : = N L 1 ( y ) L_{2,y} := N_{L_1}(y) L 2 , y := N L 1 ( y ) and L 2 , z : = N L 1 ( z ) L_{2,z} := N_{L_1}(z) L 2 , z := N L 1 ( z ) . Then, in some 3-coloring of G G G , only one color appears in either L 2 , y L_{2,y} L 2 , y or L 2 , z L_{2,z} L 2 , z (Figure 7 , right).4
This means that either G [ N ( L 2 , y ) ] G[N(L_{2,y})] G [ N ( L 2 , y )] or G [ N ( L 2 , z ) ] G[N(L_{2,z})] G [ N ( L 2 , z )] is 2-colorable (bipartite). It is known that bipartite graphs can be colored online using only O ( log n ) O(\log n) O ( log n ) colors [25 ] . Moreover, in favorable cases, both L 2 , y L_{2,y} L 2 , y and L 2 , z L_{2,z} L 2 , z are large (due to the large degree of each vertex in V ∖ S V \setminus S V ∖ S ), and hence many future vertices belong to N ( L 2 , y ) N(L_{2,y}) N ( L 2 , y ) or N ( L 2 , z ) N(L_{2,z}) N ( L 2 , z ) . As a result, we use only O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors. (To achieve O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors in all cases, [21 ] used some additional techniques.)
Next, we explain how [23 ] generalizes this algorithm to k k k -colorable graphs for general k k k . The crucial observation is that in the algorithm above, we obtain a “small” 1-chromatic subgraph (the vertex x x x ) in Step 1 and a “small” 2-chromatic subgraph (the edge { y , z } \{y, z\} { y , z } ) in Step 2. Therefore, they introduce an online subroutine LOC(k k k ) that either colors a graph effectively or terminates by returning a “small” subset X ⊆ V X \subseteq V X ⊆ V such that χ ( G [ X ] ) > k \chi(G[X]) > k χ ( G [ X ]) > k . In [23 ] , similarly to Steps 1–3 above, LOC(k k k ) is a recursive algorithm that calls LOC(0), LOC(1), … \ldots … , LOC(k − 1 k - 1 k − 1 ).
However, [23 ] cannot effectively color m 2 m^2 m 2 -colorable graphs due to this recursive structure. Let f k f_k f k be an upper bound on the size of a subgraph returned by LOC(k k k ). Then, f k ≈ f 0 × f 1 × ⋯ × f k − 1 f_k \approx f_0 \times f_1 \times\cdots\times f_{k-1} f k ≈ f 0 × f 1 × ⋯ × f k − 1 , as the returned subgraph is recursively constructed using the outputs of LOC(0), … \ldots … , LOC(k − 1 k - 1 k − 1 ). Therefore, f k f_k f k grows double-exponentially and ultimately exceeds n n n at k = Θ ( log log n ) ≤ m 2 k = \Theta(\log\log n) \leq m^2 k = Θ ( log log n ) ≤ m 2 . The
required number of colors for k k k -colorable graphs increases in proportion to f k f_k f k , so [23 ] is unsuitable for m 2 m^2 m 2 -colorable graphs.
Our Techniques
To address this issue, we attempt to “shorten” the recursion: we try to solve LOC ( k ) \operatorname{LOC}(k) LOC ( k ) by calling only LOC ( 0 ) , … , LOC ( k − m ) \operatorname{LOC}(0),\ldots,\operatorname{LOC}(k-m) LOC ( 0 ) , … , LOC ( k − m ) . This change would make f k ≈ f 0 × f 1 × ⋯ × f k − m f_k \approx f_0 \times f_1 \times\cdots\times f_{k-m} f k ≈ f 0 × f 1 × ⋯ × f k − m , and thus f m 2 = n o ( 1 ) f_{m^2}=n^{o(1)} f m 2 = n o ( 1 ) , which is sufficiently small. We achieve this by introducing a new algorithm that colors ( m + 1 ) (m+1) ( m + 1 ) -clique-free graphs online with O ( n / m ) O(n/m) O ( n / m ) colors (better than [BFS+26]) and integrating it into the recursive framework of [23 ] .
Clique-free algorithm. Our recursive algorithm for coloring k k k -clique-free graphs (2 ≤ k ≤ m + 1 2 \le k \le m+1 2 ≤ k ≤ m + 1 ) is as follows. First, prepare a limited number of bins B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … , ensuring each bin is ( k − 1 ) (k-1) ( k − 1 ) -clique-free. Then, we can color the vertices in each bin using our (recursively constructed) algorithm for ( k − 1 ) (k-1) ( k − 1 ) -clique-free graphs, using disjoint colors for different bins.
When a new vertex v v v arrives, we place v v v in a bin if a suitable bin exists. Otherwise, we color v v v using the fact that v v v is adjacent to many ( k − 2 ) (k-2) ( k − 2 ) -cliques; see Figure 8 (a). Consider two different vertices x x x and y y y outside the bins. If there is at least one ( k − 2 ) (k-2) ( k − 2 ) -clique such that both x x x and y y y are adjacent to all its vertices, then x x x and y y y are not adjacent, because otherwise the graph would not be k k k -clique-free. We exploit this no-edge property to color vertices outside the bins effectively (see Subsection 6.1–Subsection 6.2 for details).
Figure 8. (a) The state when a new vertex v v v cannot be placed in any bin. (b) The framework of our new algorithm, which iteratively restricts the number of colors allowed across a collection of cliques.
Shortening the recursion. To use the clique-free algorithm in the main problem, instead of First-Fit, we begin with a greedy-bin algorithm similar to the clique-free algorithm, in which each bin is ( m + 1 ) (m+1) ( m + 1 ) -clique-free. Then, we can force any arriving vertices outside bins to be adjacent to many m m m -cliques. Using a recursive framework similar to that of Steps 1–3, we iteratively restrict the number of colors allowed across a collection of cliques (Figure 8 (b)).
Ultimately, we aim to create a structure in which a collection of m m m -cliques, S 1 , S 2 , … , S p S_1,S_2,\ldots,S_p S 1 , S 2 , … , S p , shares the same set of m m m colors in some k k k -coloring of G G G . Then, every future vertex that is adjacent to (all m m m vertices of) at least one of these cliques must use the remaining k − m k-m k − m colors in a k k k -coloring of G G G , which is why the recursion stops at LOC ( k − m ) \operatorname{LOC}(k-m) LOC ( k − m ) . We give the details in Subsection 6.6–Subsection 6.11.
Preliminaries
We present notation, formal definitions, and a fundamental tool required in the main proof.
Notation. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. The set of vertices adjacent to a vertex v ∈ V v \in V v ∈ V is denoted by N ( v ) N(v) N ( v ) . The set of vertices adjacent to at least one vertex in a vertex set S S S is denoted by N ( S ) N(S) N ( S ) , i.e., N ( S ) = ⋃ v ∈ S N ( v ) N(S)=\bigcup_{v\in S}N(v) N ( S ) = ⋃ v ∈ S N ( v ) . For a set X ⊆ V X\subseteq V X ⊆ V , we also denote N X ( v ) = N ( v ) ∩ X N_X(v)=N(v)\cap X N X ( v ) = N ( v ) ∩ X and N X ( S ) = N ( S ) ∩ X N_X(S)=N(S)\cap X N X ( S ) = N ( S ) ∩ X . We denote G [ S ] G[S] G [ S ] as the subgraph induced by S ⊆ V S\subseteq V S ⊆ V . We denote the chromatic number by χ ( G ) \chi(G) χ ( G ) . For a positive integer n n n , we denote [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } . We generally assume base 2 for the logarithm.
Definition 3.1 (Online Coloring). In the online coloring problem, an undirected graph G = ( V , E ) G=(V,E) G = ( V , E ) starts empty; i.e., it has no vertices. The vertices of G G G are given one by one. Immediately after a vertex v v v arrives (along with all edges incident to previously arrived vertices), we must assign a color c ( v ) ∈ N c(v)\in\mathbb{N} c ( v ) ∈ N that differs from the colors of all adjacent vertices. The goal is to minimize the number of colors used, ∣ { c ( v ) : v ∈ V } ∣ |\{c(v):v\in V\}| ∣ { c ( v ) : v ∈ V } ∣ .
Definition 3.2 (Competitive Ratio). Consider a minimization problem. For an instance I I I of this problem, let ALG ( I ) \operatorname{ALG}(I) ALG ( I ) be the performance of an online algorithm and let OPT ( I ) \operatorname{OPT}(I) OPT ( I ) be the optimal (offline) performance. Then, the competitive ratio of this online algorithm is max I { ALG ( I ) / OPT ( I ) } \max_I\{\operatorname{ALG}(I)/\operatorname{OPT}(I)\} max I { ALG ( I ) / OPT ( I )} for deterministic algorithms, and max I { E [ ALG ( I ) ] / OPT ( I ) } \max_I\{\mathbb{E}[\operatorname{ALG}(I)]/\operatorname{OPT}(I)\} max I { E [ ALG ( I )] / OPT ( I )} for randomized algorithms against an oblivious adversary.
Assuming n n n and k k k are known in advance. To compute the competitive ratio of the online coloring algorithms, we must consider the case where the number of vertices n n n , and the chromatic number k k k , are not known in advance. However, by the following lemma, assuming that n n n and k k k are known in advance does not change the asymptotic order of the competitive ratio. Note that this lemma is used in § 5 and § 6 , but not in § 4 .
Lemma 3.3. Let f : N → R ≥ 0 f:\mathbb{N}\to\mathbb{R}_{\ge0} f : N → R ≥ 0 be a non-decreasing function that satisfies f ( n ) = Ω ( n 1 / 100 ) f(n)=\Omega(n^{1/100}) f ( n ) = Ω ( n 1/100 ) and f ( n ) ≤ n f(n)\le n f ( n ) ≤ n .
(i) For every n , k ≥ 1 n,k\ge1 n , k ≥ 1 , suppose that there is a deterministic online coloring algorithm A n , k \mathcal{A}_{n,k} A n , k that colors any n n n -vertex k k k -colorable graphs within k ⋅ f ( n ) k\cdot f(n) k ⋅ f ( n ) colors when n n n and k k k are known in advance. Then, there is a 96 f ( n ) 96f(n) 96 f ( n ) -competitive deterministic algorithm for online coloring. Moreover, the algorithm runs in polynomial time if each algorithm A n , k \mathcal{A}_{n,k} A n , k is run in polynomial time (with respect to n n n ).
(ii) The same claims also apply for randomized algorithms against an oblivious adversary, with the color bounds in both the assumption and the conclusion interpreted in expectation.
Proof. Consider (ii) the randomized case. For simplicity, assume that the final number of vertices n n n is known in advance at this point. Consider the following algorithm.
For d = 0 , 1 , 2 , … d=0,1,2,\ldots d = 0 , 1 , 2 , … , we process the algorithm A n , 2 d \mathcal{A}_{n,2^d} A n , 2 d while it uses at most 2 d + 2 ⋅ f ( n ) 2^{d+2}\cdot f(n) 2 d + 2 ⋅ f ( n ) colors. If coloring v v v would cause the number of colors exceeding 2 d + 2 ⋅ f ( n ) 2^{d+2}\cdot f(n) 2 d + 2 ⋅ f ( n ) , we finish A n , 2 d \mathcal{A}_{n,2^d} A n , 2 d and process later vertices with A n , 2 d + 1 \mathcal{A}_{n,2^{d+1}} A n , 2 d + 1 , starting from v v v . We use disjoint colors for different d d d .
We analyze the number of colors used. Let q : = ⌊ log 2 χ ( G ) ⌋ q:=\lfloor\log_2\chi(G)\rfloor q := ⌊ log 2 χ ( G )⌋ for the final graph G G G . Then, for i ≥ 0 i\ge0 i ≥ 0 , the algorithm A n , 2 q + i \mathcal{A}_{n,2^{q+i}} A n , 2 q + i uses expected 2 q + i f ( n ) 2^{q+i}f(n) 2 q + i f ( n ) colors, because χ ( G ) ≤ 2 q + i \chi(G)\le2^{q+i} χ ( G ) ≤ 2 q + i . By Markov’s inequality, it uses more than 2 q + i + 2 f ( n ) 2^{q+i+2}f(n) 2 q + i + 2 f ( n ) colors with probability at most 1 / 4 1/4 1/4 . Therefore, the algorithm A n , 2 q + i \mathcal{A}_{n,2^{q+i}} A n , 2 q + i starts with probability at most 1 / 4 i 1/4^i 1/ 4 i . The total expected number of colors is
∑ i = 0 q − 1 2 i + 2 f ( n ) + ∑ i = 0 ∞ ( 1 4 i ⋅ 2 q + i + 2 f ( n ) ) ≤ 2 q + 2 f ( n ) + 2 q + 3 f ( n ) = 12 ⋅ 2 q f ( n ) ≤ 24 χ ( G ) f ( n ) . \begin{aligned}
\sum_{i=0}^{q-1}2^{i+2}f(n)+\sum_{i=0}^{\infty}\left(\frac{1}{4^i}\cdot2^{q+i+2}f(n)\right)\le2^{q+2}f(n)+2^{q+3}f(n) \\
&=12\cdot2^q f(n)\le24\chi(G)f(n).
\end{aligned} i = 0 ∑ q − 1 2 i + 2 f ( n ) + i = 0 ∑ ∞ ( 4 i 1 ⋅ 2 q + i + 2 f ( n ) ) ≤ 2 q + 2 f ( n ) + 2 q + 3 f ( n ) = 12 ⋅ 2 q f ( n ) ≤ 24 χ ( G ) f ( n ) .
Now, consider the case where n n n is not known in advance. Let B n \mathcal{B}_n B n be the algorithm above when n n n is known in advance. Consider the following algorithm:
Let t i t_i t i be the largest integer such that f ( t i ) ≤ 2 i f(t_i)\le2^i f ( t i ) ≤ 2 i (or t i = 0 t_i=0 t i = 0 if no such integer exists). For the next t i t_i t i vertices or until the last vertex arrives, we use the algorithm B t i \mathcal{B}_{t_i} B t i . We use completely disjoint colors for different layer i i i .
Let i ′ = ⌈ log 2 f ( n ) ⌉ i'=\lceil\log_2 f(n)\rceil i ′ = ⌈ log 2 f ( n )⌉ . Since f ( n ) ≤ 2 i ′ f(n)\le2^{i'} f ( n ) ≤ 2 i ′ , we have t i ′ ≥ n t_{i'}\ge n t i ′ ≥ n , so the process i > i ′ i>i' i > i ′ never occurs. Let c i c_i c i be the number of colors used in the layer i i i . Since E [ c i ] ≤ 24 χ ( G ) f ( t i ) \mathbb{E}[c_i]\le24\chi(G)f(t_i) E [ c i ] ≤ 24 χ ( G ) f ( t i ) , the expected total number of colors used is
E [ ∑ i = 0 i ′ c i ] ≤ ∑ i = 0 i ′ 24 χ ( G ) f ( t i ) ≤ 24 χ ( G ) ∑ i = 0 i ′ 2 i ≤ 24 χ ( G ) ⋅ 2 i ′ + 1 ≤ 96 χ ( G ) f ( n ) . \mathbb{E}\left[\sum_{i=0}^{i'}c_i\right]\le\sum_{i=0}^{i'}24\chi(G)f(t_i)\le24\chi(G)\sum_{i=0}^{i'}2^i\le24\chi(G)\cdot2^{i'+1}\le96\chi(G)f(n). E i = 0 ∑ i ′ c i ≤ i = 0 ∑ i ′ 24 χ ( G ) f ( t i ) ≤ 24 χ ( G ) i = 0 ∑ i ′ 2 i ≤ 24 χ ( G ) ⋅ 2 i ′ + 1 ≤ 96 χ ( G ) f ( n ) .
Therefore, we attain an (expected) competitive ratio of 96 f ( n ) 96f(n) 96 f ( n ) . The deterministic case can also be proved analogously. Finally, this algorithm run in polynomial time because B k \mathcal{B}_k B k is obviously polynomial time and t i = O ( n 100 ) t_i=O(n^{100}) t i = O ( n 100 ) when n n n is large enough. □
The Lower Bound for Deterministic Algorithms
In this section, we prove that any deterministic online coloring algorithm has competitive ratio Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) . To this end, we consider to what extent we can “force” the algorithm to use each color in at most two vertices.
Halldórsson and Szegedy’s Model and its Limitations
The worst-case performance of deterministic online algorithms can be discussed in the context of an adversarial attack against a player. In online coloring, the adversary decides the set of incident edges of each new vertex v v v , adaptively, by looking at the player’s coloring so far.
Transparent model. We assume that the graph is k k k -colorable. To obtain a lower bound on the competitive ratio, Halldórsson and Szegedy [17 ] [17 ] considered a model in which the adversary maintains a k k k -coloring of the graph, φ : V → { 1 , … , k } \varphi:V\to\{1,\ldots,k\} φ : V → { 1 , … , k } , online. To distinguish it from the colors that the player assigns, we call the colors used in φ \varphi φ the base colors .
Step 1. The adversary decides the set of edges incident to a new vertex v v v .
Step 2. The player assigns its color c ( v ) ∈ N c(v)\in\mathbb{N} c ( v ) ∈ N .
Step 3. The adversary decides its base color φ ( v ) ∈ { 1 , … , k } \varphi(v) \in\{1,\ldots,k\} φ ( v ) ∈ { 1 , … , k } in response to the player. This must differ from the base colors of all its neighbors. φ ( v ) \varphi(v) φ ( v ) cannot be changed in the future.
This is called the transparent model because we assume that the player can also see the k k k -coloring φ \varphi φ . Apparently, the best strategy in Step 1 is to choose an admissible set of base colors
X v ⊆ { 1 , … , k } : X_v \subseteq\{1,\ldots,k\} : X v ⊆ { 1 , … , k } :
the set of base colors that can be assigned to v v v (in Step 3)
and make all the previous vertices with base colors in { 1 , … , k } ∖ X v \{1,\ldots,k\} \setminus X_v { 1 , … , k } ∖ X v adjacent to v v v , because player can also see φ \varphi φ . See Figure 9 (a) for the illustration of this model.
Figure 9. Examples of (a) transparent model and (b) our new model. We write ? for the vertices whose base color is currently unassigned. For the new model, we leave the base color unassigned for vertices whose online colors are currently used in just one vertex.
Compared to ordinary online coloring, the transparent model is handicapped for the adversary; indeed, the adversary must irrevocably assign each base color in Step 3, and the player is given additional information about base coloring. However, it can still force the player to use many colors, as shown below, implying an Ω ( n / log 2 n ) \Omega(n/\log^{2} n) Ω ( n / log 2 n ) lower bound on the competitive ratio.
Theorem 4.1 ([17 ] ). Let k ≥ 1 k \ge1 k ≥ 1 be an integer. In the transparent model, the adversary has a strategy that forces the player to use 2 k − 1 2^k-1 2 k − 1 colors on a k k k -colorable graph with k ⋅ 2 k − 1 k \cdot2^{k-1} k ⋅ 2 k − 1 vertices.
Limitations. On the other hand, the player has a strategy that uses at most 2 k − 1 2^k-1 2 k − 1 colors for any k k k -colorable input in the transparent model, which shows the tightness of the result above. In particular, [17 Section 4.5] discusses a player strategy that yields the following outcome.
Theorem 4.2 ([17 ] , restated). For each color c ∈ N c \in\mathbb{N} c ∈ N , let T c ⊆ { 1 , … , k } T_c \subseteq\{1,\ldots,k\} T c ⊆ { 1 , … , k } be the current set of base colors used on vertices of an (online) color c c c . There exists a strategy for the player that maintains the condition that “the sets T c T_c T c are distinct over all present (online) colors c c c ”.
This also implies that Θ ( n / log 2 n ) \Theta(n/\log^{2} n) Θ ( n / log 2 n ) is indeed the optimal competitive ratio for the transparent model [17 ] . More importantly, under the transparent model, the adversary cannot force the player to use each color in at most two vertices for more than k ( k + 1 ) k(k+1) k ( k + 1 ) vertices. This is due to Theorem 4.2 and that there are 1 2 k ( k + 1 ) \frac{1}{2}k(k+1) 2 1 k ( k + 1 ) distinct non-empty subsets of { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } with size at most two. This O ( k 2 ) O(k^2) O ( k 2 ) -vertex limit is far from our exponential goal. To obtain a better bound, we need a new model that does not decide the k k k -coloring φ \varphi φ immediately.
New Adversary Model
We consider an adversary strategy to avoid creating the “third vertex” of the same color. The goal of this subsection is to prove the following lemma.
Lemma 4.3. Let ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 be an integer. The adversary has a strategy that forces the player to use each color in at most two vertices on a 2 ℓ 2\ell 2 ℓ -colorable graph with 2 ℓ 2^\ell 2 ℓ vertices.
Proof. Below, we give a simple proof. Assuming each color is used in at most two vertices, we say that a vertex is paired if another vertex has the same color, and otherwise unpaired .
The new model. We modify the transparent model by postponing the assignment of base colors while constructing a 2 ℓ 2\ell 2 ℓ -coloring φ \varphi φ . When the first vertex v 1 v_1 v 1 of a certain color arrives, we do not fix its base color φ ( v 1 ) \varphi(v_1) φ ( v 1 ) . When the second vertex v 2 v_2 v 2 of this color arrives, we fix the base colors of both paired vertices, φ ( v 1 ) \varphi(v_1) φ ( v 1 ) and φ ( v 2 ) \varphi(v_2) φ ( v 2 ) , simultaneously. When deciding the base colors of two newly paired vertices, we impose a new rule: the adversary must choose s ∈ { 1 , … , ℓ } s \in\{1,\ldots,\ell\} s ∈ { 1 , … , ℓ } and assign base color 2 s − 1 2s-1 2 s − 1 to one of them and 2 s 2s 2 s to the other (e.g., s = 2 s=2 s = 2 for Figure 9 (b)).
Adversary algorithm. We consider the adversary proceeding as follows:
When deciding the set of edges incident to each vertex v v v , similar to the transparent model, they first choose the set of its admissible base colors X v ⊆ { 1 , … , 2 ℓ } X_v \subseteq\{1,\ldots,2\ell\} X v ⊆ { 1 , … , 2 ℓ } , where for each s ∈ { 1 , … , ℓ } s \in\{1,\ldots,\ell\} s ∈ { 1 , … , ℓ } , exactly one of { 2 s − 1 , 2 s } \{2s-1,2s\} { 2 s − 1 , 2 s } must be in X v X_v X v . Then, they make all the previous paired vertices with base colors in { 1 , … , 2 ℓ } ∖ X v \{1,\ldots,2\ell\} \setminus X_v { 1 , … , 2 ℓ } ∖ X v adjacent to v v v . No edges are added to unpaired vertices. With this method, it is impossible for the player to select an online color that has already been used on two vertices (see Figure 10 for examples). Importantly, the adversary must choose different X v X_v X v for each vertex v v v ; however, this is possible because X v X_v X v has 2 ℓ 2^\ell 2 ℓ possible subsets.
Figure 10. The edges incident to v v v in four cases of X v X_v X v . In all four cases, the player cannot select online colors already used in two vertices (colors 1, 2, 4), which makes impossible to create the “third vertex”. The graphs are created for explanation and contains more than 2 ℓ 2^\ell 2 ℓ vertices.
When deciding the base color of a new pair of vertices v 1 v_1 v 1 and v 2 v_2 v 2 , we choose s s s such that 2 s − 1 2s-1 2 s − 1 is in exactly one of { X v 1 , X v 2 } \{X_{v_1},X_{v_2}\} { X v 1 , X v 2 } , and 2 s 2s 2 s is in the other. Then, if 2 s − 1 ∈ X v 1 2s-1 \in X_{v_1} 2 s − 1 ∈ X v 1 , we assign φ ( v 1 ) ← 2 s − 1 \varphi(v_1) \leftarrow2s-1 φ ( v 1 ) ← 2 s − 1 and φ ( v 2 ) ← 2 s \varphi(v_2) \leftarrow2s φ ( v 2 ) ← 2 s (and the reverse if 2 s ∈ X v 1 2s \in X_{v_1} 2 s ∈ X v 1 ). Note that such an s s s always exists due to X v 1 ≠ X v 2 X_{v_1} \ne X_{v_2} X v 1 = X v 2 (by the distinctness of X v X_v X v ). This method always satisfies the condition written at the end of “The new model” section.
Correctness. Finally, we show the constructed graph is always 2 ℓ 2\ell 2 ℓ -colorable. For analysis, for each vertex v v v whose base color remains unassigned, consider assigning φ ( v ) \varphi(v) φ ( v ) to an arbitrary element of X v X_v X v . Then, φ ( u 1 ) ≠ φ ( u 2 ) \varphi(u_1) \ne\varphi(u_2) φ ( u 1 ) = φ ( u 2 ) always holds for every two adjacent vertices u 1 , u 2 u_1,u_2 u 1 , u 2 (where u 1 u_1 u 1 arrives earlier than u 2 u_2 u 2 ) whose base colors are assigned. The reason is as follows:
First, φ ( u 2 ) ∈ X u 2 \varphi(u_2) \in X_{u_2} φ ( u 2 ) ∈ X u 2 holds by our assignment rule. Second, φ ( u 1 ) ∉ X u 2 \varphi(u_1) \notin X_{u_2} φ ( u 1 ) ∈ / X u 2 holds. This is because u 1 u_1 u 1 must already be paired when u 2 u_2 u 2 arrives (due to “The new model”) and our edge-construction rule. Thus, φ ( u 1 ) ≠ φ ( u 2 ) \varphi(u_1) \ne\varphi(u_2) φ ( u 1 ) = φ ( u 2 ) .
Since φ ( v ) ∈ { 1 , … , 2 ℓ } \varphi(v) \in\{1,\ldots,2\ell\} φ ( v ) ∈ { 1 , … , 2 ℓ } for all v v v , the constructed graph is 2 ℓ 2\ell 2 ℓ -colorable. The player cannot use the same online color on three vertices (see “Adversary algorithm” paragraph), so Lemma 4.3 holds. □
Competitive Ratio
With Lemma 4.3 , we can immediately derive an Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) lower bound on the competitive ratio.
Theorem 1.1. Every deterministic online coloring algorithm is Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) -competitive.
Proof. We prove that the competitive ratio is Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) even if the final number of vertices n ≥ 2 n \ge2 n ≥ 2 is known. We apply Lemma 4.3 with ℓ = ⌈ log 2 n ⌉ \ell=\lceil\log_2 n\rceil ℓ = ⌈ log 2 n ⌉ ; note that n ≤ 2 ℓ n \le2^\ell n ≤ 2 ℓ . Then, for every deterministic algorithm, there exists an input of an n n n -vertex 2 ℓ 2\ell 2 ℓ -colorable graph such that this algorithm uses at least n / 2 n/2 n /2 colors. This gives a lower bound of n / 2 2 ⌈ log 2 n ⌉ = Ω ( n / log n ) \frac{n/2}{2^{\lceil\log_2 n\rceil}}=\Omega(n/\log n) 2 ⌈ l o g 2 n ⌉ n /2 = Ω ( n / log n ) on the competitive ratio. □
The Upper Bound for Randomized Algorithms
In this section, we present a randomized online coloring algorithm that attains a competitive ratio of O ( n ( log log n ) 2 / ( log n ) 2 ) O(n(\log\log n)^2/(\log n)^2) O ( n ( log log n ) 2 / ( log n ) 2 ) , assuming an oblivious adversary. This significantly closes the gap to an Ω ( n / log 2 n ) \Omega(n/\log^2 n) Ω ( n / log 2 n ) lower bound given by Halldórsson and Szegedy [17 ] .
Can We Use the Third Vertex?
In the introduction, we showed that Algorithm 1 uses only n / 2 + o ( n ) n/2+o(n) n /2 + o ( n ) colors, with each color on at most two vertices, if the chromatic number is not too large (Proposition 1.4 ). This raises a natural question: “if the chromatic number is not too large, can we use only n / 3 + o ( n ) n/3+o(n) n /3 + o ( n ) colors, each on at most three vertices?” This means that most colors must be used exactly three times.
In § 4 , we have proved that this is impossible for deterministic algorithms: even for O ( log n ) O(\log n) O ( log n ) -colorable graphs, the adversary can force all colors to be used on at most two vertices. However, for randomized algorithms, the answer is yes for graphs with chromatic number o ( n 1 / 2 ) o(n^{1/2}) o ( n 1/2 ) , and we show our intuition below.
The power of randomization. First, consider the most natural extension of Algorithm 1. For each vertex v ∈ V v \in V v ∈ V , (1) use a color used in two vertices if possible; (2) otherwise, use a color used in one vertex if possible; (3) otherwise, use a fresh color. Unfortunately, this algorithm fails on a bipartite graph example given in the Introduction section (Figure 1 ), where no color is used on three vertices.
However, with the power of randomization, this barrier can be addressed. Consider a new algorithm that occasionally uses a fresh color even if (2) is possible. Then, in the previous example (Figure 1 ), many colors can be used on three vertices. This is because the randomization changes “which pairs of two vertices end up sharing the same color” (note that, in the previous deterministic case, the pairing is always between the ( 2 i − 1 ) (2i-1) ( 2 i − 1 ) -th arrived vertex and the 2 i 2i 2 i -th arrived vertex, and this is exactly why we cannot use the same color in three vertices). This is the intuition for why randomization is strong.
In the following two subsections, we introduce an algorithm that achieves n / 3 + o ( n ) n/3 + o(n) n /3 + o ( n ) colors in expectation when the chromatic number is o ( n 1 / 2 ) o(n^{1/2}) o ( n 1/2 ) .
Notation and Assumptions
We use G ∗ = ( V ∗ , E ∗ ) G^* = (V^*, E^*) G ∗ = ( V ∗ , E ∗ ) to denote the final graph, distinguishing it from the current graph used for online coloring. For v 1 , v 2 ∈ V ∗ v_1, v_2 \in V^* v 1 , v 2 ∈ V ∗ , we write v 1 ≺ v 2 v_1 \prec v_2 v 1 ≺ v 2 if v 1 v_1 v 1 arrives before v 2 v_2 v 2 . We use the constant e ≈ 2.718 e \approx2.718 e ≈ 2.718 . The following definitions are extensively used in the following subsections.
Let ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 be an integer. We call a color that is (currently) used in exactly ℓ \ell ℓ vertices “a level-ℓ \ell ℓ color”. We call a vertex with a level-ℓ \ell ℓ color “a level-ℓ \ell ℓ vertex”.
We assume that G ∗ G^* G ∗ is k k k -colorable. For the analysis, we fix a k k k -coloring φ : V ∗ → { 1 , … , k } \varphi: V^* \to\{1, \ldots, k\} φ : V ∗ → { 1 , … , k } of G ∗ G^* G ∗ . To distinguish it from the (online) colors used in the algorithm, we call the colors used in φ \varphi φ the “base colors”. In addition, we say that an (online) color c c c is “eligible” for a new vertex v v v if and only if v v v is not adjacent to any previously arrived vertex whose online color is c c c .
Three-Level Algorithm
We consider the following “three-level” algorithm, which upgrades the “two-level” algorithm of Algorithm 1. We use an integer parameter θ ≥ 1 \theta\ge1 θ ≥ 1 as a threshold. For each vertex v ∈ V ∗ v \in V^* v ∈ V ∗ :
If there is an eligible level-2 color, we assign this color to v v v .
Otherwise, if there are at least θ \theta θ eligible level-1 colors, we choose one of them uniformly at random and assign this color to v v v .
Otherwise, we assign a fresh color to v v v .
See Figure 6 for the illustration. With an appropriate setting of parameter θ \theta θ , this algorithm uses only n / 3 + o ( n ) n/3 + o(n) n /3 + o ( n ) colors in expectation for k k k -colorable graphs with k = o ( n ) k = o(\sqrt{n}) k = o ( n ) . Below, we analyze this algorithm by estimating the expected number of level-1 and level-2 colors.
Lemma 5.1. In the final state, there are at most k θ k\theta k θ level-1 colors.
Proof. If there are k θ + 1 k\theta+ 1 k θ + 1 or more level-1 vertices, the pigeonhole principle implies there are θ + 1 \theta+ 1 θ + 1 level-1 vertices v 1 , … , v θ + 1 v_1, \ldots, v_{\theta+1} v 1 , … , v θ + 1 (in arriving order) with the same base color φ ( v i ) \varphi(v_i) φ ( v i ) . Since v θ + 1 v_{\theta+1} v θ + 1 is not adjacent to v 1 , … , v θ v_1, \ldots, v_\theta v 1 , … , v θ , the vertex v θ + 1 v_{\theta+1} v θ + 1 should have been colored by Step 2 (or Step 1), which is a contradiction. Therefore, Lemma 5.1 holds.
Bounding level-2 colors. Next, we bound the number of level-2 colors. First, we list the vertices of the (final) level-2 colors as
( a 1 , b 1 ) , … , ( a m , b m ) ( a 1 ≺ b 1 , … , a m ≺ b m ; b 1 ≺ ⋯ ≺ b m ) , (a_1,b_1),\ldots,(a_m,b_m) \quad(a_1 \prec b_1,\ldots,a_m \prec b_m; b_1 \prec\cdots\prec b_m), ( a 1 , b 1 ) , … , ( a m , b m ) ( a 1 ≺ b 1 , … , a m ≺ b m ; b 1 ≺ ⋯ ≺ b m ) ,
where a i a_i a i and b i b_i b i have the same color for each i ∈ { 1 , … , m } i \in\{1,\ldots,m\} i ∈ { 1 , … , m } . Below, we refer to this list as “the pairing”. We upper bound the probability that there are exactly m m m level-2 colors in the following way: (i) bounding the probability that a fixed pairing of size m m m occurs (Lemma 5.2 ), and (ii) bounding the number of “valid” pairings of size m m m (Lemma 5.3 ).
Lemma 5.2. The probability that the pairing becomes ( a 1 , b 1 ) , … , ( a m , b m ) (a_1,b_1),\ldots,(a_m,b_m) ( a 1 , b 1 ) , … , ( a m , b m ) is at most 1 / θ m 1/\theta^m 1/ θ m .
Proof. When vertex b i b_i b i arrives, the probability that the same color as a i a_i a i is chosen to become a level-2 vertex is at most 1 / θ 1/\theta 1/ θ , since there are at least θ \theta θ color choices (see Figure 11 (a)). Therefore, this happens to all i = 1 , … , m i=1,\ldots,m i = 1 , … , m with probability at most 1 / θ m 1/\theta^m 1/ θ m . □
Figure 11. A sketch of our proof deriving the probability that there are exactly m m m level-2 colors. In (b), each line between two vertices represents an edge of the graph.
Lemma 5.3. The number of pairings of size m m m that occur with non-zero probability is at most k m ⋅ ( n m ) 2 k^m \cdot\binom{n}{m}^{2} k m ⋅ ( m n ) 2 .
Proof. We prove that, for fixed sets A , B ⊆ V ∗ A,B \subseteq V^* A , B ⊆ V ∗ with ∣ A ∣ = ∣ B ∣ = m |A|=|B|=m ∣ A ∣ = ∣ B ∣ = m , there are at most k m k^m k m pairings with { a 1 , … , a m } = A \{a_1,\ldots,a_m\}=A { a 1 , … , a m } = A and { b 1 , … , b m } = B \{b_1,\ldots,b_m\}=B { b 1 , … , b m } = B (out of m ! m! m ! possibilities) that occur with non-zero probability. This is enough to prove Lemma 5.3 because there are at most ( n m ) 2 \binom{n}{m}^{2} ( m n ) 2 choices for ( A , B ) (A,B) ( A , B ) .
Each vertex a ∈ A a \in A a ∈ A can be paired with b ∈ B b \in B b ∈ B only if there exists some i ∈ { 1 , … , k } i \in\{1,\ldots,k\} i ∈ { 1 , … , k } such that b b b is the last vertex with base color i i i among the vertices that are not adjacent to a a a in B B B . The reasons are as follows. If no such i i i exists, this means that there exists a vertex b ′ b' b ′ (b ≺ b ′ b \prec b' b ≺ b ′ , φ ( b ) = φ ( b ′ ) \varphi(b)=\varphi(b') φ ( b ) = φ ( b ′ ) ) such that b ′ b' b ′ is not adjacent to a a a . Here, we observe that b ′ b' b ′ is also not adjacent to b b b , because of φ ( b ) = φ ( b ′ ) \varphi(b)=\varphi(b') φ ( b ) = φ ( b ′ ) . Therefore, since a a a and b b b have the same level-2 color c c c , the color c c c is eligible for b ′ b' b ′ , and our algorithm makes b ′ b' b ′ a level-3 vertex, a contradiction. Hence, there are at most k k k choices for each a ∈ A a \in A a ∈ A , and at most k m k^m k m valid pairings (see Figure 11 (b)). □
Lemma 5.4. In the final state, there are at most e n 2 k / θ + 2 en\sqrt{2k/\theta}+2 e n 2 k / θ + 2 level-2 colors in expectation.
Proof. Let X X X be the random variable describing the size of pairings (i.e. the number of level-2 colors). By Lemma 5.2 and Lemma 5.3 ,
Pr [ X = m ] ≤ 1 θ m ⋅ { k m ⋅ ( n m ) 2 } ≤ ( e 2 k n 2 θ m 2 ) m (1) \Pr[X=m] \le\frac{1}{\theta^m}\cdot\left\{k^m\cdot\binom{n}{m}^{2}\right\}\le\left(\frac{e^2kn^2}{\theta m^2}\right)^m \tag*{(1)} Pr [ X = m ] ≤ θ m 1 ⋅ { k m ⋅ ( m n ) 2 } ≤ ( θ m 2 e 2 k n 2 ) m (1)
due to ( n m ) ≤ ( e n / m ) m \binom{n}{m} \le(en/m)^m ( m n ) ≤ ( e n / m ) m . By Equation (1) , Pr [ X = m ] ≤ 1 / 2 m \Pr[X=m] \le1/2^m Pr [ X = m ] ≤ 1/ 2 m holds for all integers m ≥ e n 2 k / θ m \ge en\sqrt{2k/\theta} m ≥ e n 2 k / θ . Therefore, the expected value of X X X is
E [ X ] = ∑ i = 1 ⌈ e n 2 k / θ ⌉ − 1 i ⋅ Pr [ X = i ] + ∑ i = ⌈ e n 2 k / θ ⌉ ∞ i ⋅ Pr [ X = i ] ≤ e n 2 k θ + ∑ i = 1 ∞ ( i ⋅ 1 2 i ) = e n 2 k θ + 2. \begin{aligned}
\mathbb{E}[X] = \sum_{i=1}^{\lceil en\sqrt{2k/\theta}\rceil-1} i \cdot\Pr[X=i] + \sum_{i=\lceil en\sqrt{2k/\theta}\rceil}^{\infty} i \cdot\Pr[X=i] \\
&\le en\sqrt{\frac{2k}{\theta}} + \sum_{i=1}^{\infty}\left(i\cdot\frac{1}{2^i}\right) = en\sqrt{\frac{2k}{\theta}} + 2.
\end{aligned} E [ X ] = i = 1 ∑ ⌈ e n 2 k / θ ⌉ − 1 i ⋅ Pr [ X = i ] + i = ⌈ e n 2 k / θ ⌉ ∑ ∞ i ⋅ Pr [ X = i ] ≤ e n θ 2 k + i = 1 ∑ ∞ ( i ⋅ 2 i 1 ) = e n θ 2 k + 2.
This proves that the expected number of level-2 colors is at most e n 2 k / θ + 2 en\sqrt{2k/\theta}+2 e n 2 k / θ + 2 .
With these bounds on the number of level-1 and level-2 colors, we finally complete the analysis for the number of colors used, with an appropriate parameter setting of θ \theta θ . The theorem below also implies that we use at most ( 1 + o ( 1 ) ) n / 3 (1+o(1))n/3 ( 1 + o ( 1 )) n /3 colors when k = o ( n ) k=o(\sqrt{n}) k = o ( n ) .
Theorem 5.5. The algorithm uses at most n / 3 + O ( n 2 / 3 k 2 / 3 ) n/3+O(n^{2/3}k^{2/3}) n /3 + O ( n 2/3 k 2/3 ) colors in expectation, when n n n and k k k are known in advance, with an appropriate setting of the parameter θ \theta θ .
Proof. If there are c 1 c_1 c 1 level-1 colors and c 2 c_2 c 2 level-2 colors, the total number of colors is c 1 + c 2 + ( n − c 1 − 2 c 2 ) / 3 = 1 3 n + 2 3 c 1 + 1 3 c 2 c_1+c_2+(n-c_1-2c_2)/3=\frac{1}{3}n+\frac{2}{3}c_1+\frac{1}{3}c_2 c 1 + c 2 + ( n − c 1 − 2 c 2 ) /3 = 3 1 n + 3 2 c 1 + 3 1 c 2 . By Lemma 5.1 and Lemma 5.4, in expectation, this is at most
n 3 + 2 3 k θ + 1 3 ( e n 2 k θ + 2 ) . \frac{n}{3}+\frac{2}{3}k\theta+\frac{1}{3}\left(en\sqrt{\frac{2k}{\theta}}+2\right). 3 n + 3 2 k θ + 3 1 ( e n θ 2 k + 2 ) . This value is n / 3 + ( e n k ) 2 / 3 + 2 / 3 n/3+(enk)^{2/3}+2/3 n /3 + ( e nk ) 2/3 + 2/3 with the optimal parameter setting θ = { e 2 n 2 / ( 8 k ) } 1 / 3 \theta=\{e^2n^2/(8k)\}^{1/3} θ = { e 2 n 2 / ( 8 k ) } 1/3 . Although θ \theta θ must be an integer, the asymptotic order is unchanged. □
General-Level Algorithm
The next task is to increase the number of vertices per color from 3 to a larger fixed d d d (d = 4 , 5 , … d=4,5,\ldots d = 4 , 5 , … ), generalizing the “three-level” algorithm in Subsection 5.3.
Algorithm. We set the threshold parameters θ 1 , … , θ d − 1 \theta_1,\ldots,\theta_{d-1} θ 1 , … , θ d − 1 , which are all positive integers. For each vertex v ∈ V ∗ v\in V^* v ∈ V ∗ , we select the largest integer i ∈ { d − 1 , … , 2 , 1 } i\in\{d-1,\ldots,2,1\} i ∈ { d − 1 , … , 2 , 1 } such that there are at least θ i \theta_i θ i eligible level-i i i colors (see Subsection 5.2 for “eligible”). Then we choose one eligible level-i i i color uniformly at random, and assign it to v v v . If no such i i i exists, we assign a fresh color for v v v (or more formally, the smallest unused color). The pseudocode is provided in Algorithm 2.
Analysis Part I: Grouping the Colorings
In the following two subsections, we aim to prove that when the chromatic number is k = o ( n 1 / ( d − 1 ) ) k=o(n^{1/(d-1)}) k = o ( n 1/ ( d − 1 ) ) , Algorithm 2 uses ( 1 + o ( 1 ) ) n / d (1+o(1))n/d ( 1 + o ( 1 )) n / d colors with a parameter setting θ t = ⌊ n 1 − 1 d − 1 ⌋ \theta_t=\lfloor n^{1-\frac{1}{d-1}}\rfloor θ t = ⌊ n 1 − d − 1 1 ⌋ for each t t t . First, we analyze the number of level-1 colors.
Lemma 5.6. In the final state of Algorithm 2, there are at most k θ 1 k\theta_1 k θ 1 level-1 colors.
Algorithm 2 A d d d -level algorithm for online coloring, with parameters θ d − 1 , … , θ 2 , θ 1 ≥ 1 \theta_{d-1},\ldots,\theta_2,\theta_1 \ge1 θ d − 1 , … , θ 2 , θ 1 ≥ 1 . In the description below, the level-i i i colors are the colors that are currently used on exactly i i i vertices, and a color is “eligible” if v v v is not adjacent to any vertex of this color.
for each arrival of a vertex v v v do
for i = d − 1 , … , 2 , 1 i=d-1,\ldots,2,1 i = d − 1 , … , 2 , 1 do
if there are at least θ i \theta_i θ i eligible level-i i i colors then
c ( v ) ← c(v) \leftarrow c ( v ) ← a color among eligible level-i i i colors, selected uniformly at random
Color v v v with color c ( v ) c(v) c ( v )
break
if v v v is not yet colored then
Color v v v with the smallest unused color
Proof. This follows from the same argument as Lemma 5.1 , utilizing the pigeonhole principle. □
Next, we analyze the number of level-t t t colors for a fixed t ∈ { 2 , … , d − 1 } t \in\{2,\ldots,d-1\} t ∈ { 2 , … , d − 1 } . To this end, for each fixed m m m , we bound the probability that there are exactly m m m level-t t t colors, and show that it is extremely rare when m m m is sufficiently large. To show the rarity of m m m being large, we bound the probability that the “last vertex” of each level-t t t colors is listed as b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m , for each fixed { b 1 , … , b m } ⊆ V \{b_1,\ldots,b_m\} \subseteq V { b 1 , … , b m } ⊆ V (b 1 ≺ ⋯ ≺ b m b_1 \prec\cdots\prec b_m b 1 ≺ ⋯ ≺ b m ).
Preliminaries. As mentioned in Subsection 5.2, we fix the “base coloring” φ : V ∗ → { 1 , … , k } \varphi: V^* \to\{1,\ldots,k\} φ : V ∗ → { 1 , … , k } , a k k k -coloring of G ∗ G^* G ∗ , for the purpose of the analysis. Meanwhile, the final (online) coloring is denoted by c : V ∗ → N c: V^* \to\mathbb{N} c : V ∗ → N , which is a random variable based on the choices in Algorithm 2, and we denote
C a l l : = { c ′ : V ∗ → N ∣ Pr [ c = c ′ ] > 0 , the last vertex of each level- t color is b 1 , … , b m in c ′ } \mathcal{C}_{\mathrm{all}} := \{c' : V^* \to\mathbb{N} \mid\Pr[c=c']>0,\ \text{the last vertex of each level-}t\text{ color is }b_1,\ldots,b_m\text{ in }c'\} C all := { c ′ : V ∗ → N ∣ Pr [ c = c ′ ] > 0 , the last vertex of each level- t color is b 1 , … , b m in c ′ }
which represents the set of “possible” colorings where the last vertex of each level-t t t colors is listed as b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m . We also denote the set of vertices earlier than b i b_i b i by V ≺ b i : = { v ∈ V ∗ : v ≺ b i } V_{\prec b_i}:=\{v\in V^*:v\prec b_i\} V ≺ b i := { v ∈ V ∗ : v ≺ b i } .
Definition 5.7. A subset C ⊆ C a l l \mathcal{C}\subseteq\mathcal{C}_{\mathrm{all}} C ⊆ C all is called a “good set” if it satisfies the following for all i = 1 , … , m i=1,\ldots,m i = 1 , … , m :
Condition: For every (partial) coloring c − : V ≺ b i → N c^-:V_{\prec b_i}\to\mathbb{N} c − : V ≺ b i → N that can be extended to some colorings in C \mathcal{C} C , all such extensions c ∈ C c\in\mathcal{C} c ∈ C assign the same color to the vertex b i b_i b i .
Note that for any partial coloring c − c^- c − that can be extended to some coloring in C \mathcal{C} C , Algorithm 2 must choose a level-( t − 1 ) (t-1) ( t − 1 ) color when coloring b i b_i b i due to C ⊆ C a l l \mathcal{C}\subseteq\mathcal{C}_{\mathrm{all}} C ⊆ C all .
Lemma 5.8. For every good set C ⊆ C a l l \mathcal{C}\subseteq\mathcal{C}_{\mathrm{all}} C ⊆ C all , we have Pr [ c ∈ C ] ≤ 1 / θ t − 1 m \Pr[c\in\mathcal{C}]\le1/\theta_{t-1}^m Pr [ c ∈ C ] ≤ 1/ θ t − 1 m .
Proof. Let i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } . Suppose that, just before the vertex b i b_i b i arrives, there is a (non-zero) possibility that the final coloring c : V ∗ → N c:V^*\to\mathbb{N} c : V ∗ → N satisfies c ∈ C c\in\mathcal{C} c ∈ C .
Then, the probability that c ∈ C c\in\mathcal{C} c ∈ C remains possible after coloring b i b_i b i is at most 1 / θ t − 1 1/\theta_{t-1} 1/ θ t − 1 , conditional on the state before b i b_i b i arrives. This is because the algorithm always chooses a level-( t − 1 ) (t-1) ( t − 1 ) color for the vertex b i b_i b i (as noted in Definition 5.7), and to preserve the possibility of c ∈ C c\in\mathcal{C} c ∈ C , the algorithm must choose the correct one among at least θ t − 1 \theta_{t-1} θ t − 1 choices. Finally, Lemma 5.8 holds by applying these bounds successively for i = 1 , … , m i=1,\ldots,m i = 1 , … , m . □
Our strategy. Now, we explain the proof strategy. Our core strategy is to partition C a l l \mathcal{C}_{\mathrm{all}} C all into a finite number of good sets C λ \mathcal{C}_{\lambda} C λ (λ ∈ Λ \lambda\in\Lambda λ ∈ Λ ) (where Λ \Lambda Λ is a finite set); see Figure 12 for an illustration. Due to Lemma 5.8, if we successfully partitioned C a l l \mathcal{C}_{\mathrm{all}} C all into ∣ Λ ∣ |\Lambda| ∣Λ∣ good sets, then the probability of being exactly m m m level-t t t colors is at most ( n m ) ⋅ ∣ Λ ∣ ⋅ ( 1 / θ t − 1 m ) \binom{n}{m} \cdot|\Lambda| \cdot(1/\theta_{t-1}^{m}) ( m n ) ⋅ ∣Λ∣ ⋅ ( 1/ θ t − 1 m ) , where the first ( n m ) \binom{n}{m} ( m n ) comes from the number of possible sets { b 1 , … , b m } \{b_1,\ldots,b_m\} { b 1 , … , b m } (note that we fix the set { b 1 , … , b m } \{b_1,\ldots,b_m\} { b 1 , … , b m } to define C a l l \mathcal{C}_{\mathrm{all}} C all ). Indeed, a similar strategy was already used in the previous three-level case, as follows.
Figure 12. An illustration of our strategy. (*) The colorings in (a) are toy examples created just for illustration, and do not necessarily represent possible outputs of Algorithm 2. In particular, some colorings (e.g., 1–3–1–4) have zero probability.
Subsection 5.3 considered situations that the “pairing” is ( a 1 , b 1 ) , … , ( a m , b m ) (a_1,b_1),\ldots,(a_m,b_m) ( a 1 , b 1 ) , … , ( a m , b m ) . Let Λ \Lambda Λ be the set of all possible tuples ( a 1 , … , a m ) (a_1,\ldots,a_m) ( a 1 , … , a m ) , and for each λ = ( a 1 , … , a m ) ∈ Λ \lambda=(a_1,\ldots,a_m)\in\Lambda λ = ( a 1 , … , a m ) ∈ Λ , let C λ \mathcal{C}_{\lambda} C λ be the set of final possible colorings whose pairing is ( a 1 , b 1 ) , … , ( a m , b m ) (a_1,b_1),\ldots,(a_m,b_m) ( a 1 , b 1 ) , … , ( a m , b m ) . Then, it is (virtually) proved that C λ \mathcal{C}_{\lambda} C λ is a good set in Lemma 5.2 , and that ∣ Λ ∣ ≤ k m ⋅ ( n m ) |\Lambda|\leq k^m\cdot\binom{n}{m} ∣Λ∣ ≤ k m ⋅ ( m n ) in Lemma 5.3 . These properties yield Pr [ X = m ] ≤ ( n m ) ⋅ { k m ⋅ ( n m ) } ⋅ ( 1 / θ t − 1 m ) \Pr[X=m]\leq\binom{n}{m}\cdot\{k^m\cdot\binom{n}{m}\}\cdot(1/\theta_{t-1}^{m}) Pr [ X = m ] ≤ ( m n ) ⋅ { k m ⋅ ( m n ) } ⋅ ( 1/ θ t − 1 m ) as shown in the beginning of Lemma 5.4 .
To construct the partition for the general-level case, we define the “profile tuple” as follows.
Definition 5.9 (Profile tuple). Consider a coloring c ′ ∈ C a l l c'\in\mathcal{C}_{\mathrm{all}} c ′ ∈ C all . Let A 1 , A 2 , … A_1,A_2,\ldots A 1 , A 2 , … be the set of the “first t − 1 t-1 t − 1 vertices” for each color that is used at least t − 1 t-1 t − 1 times in c ′ c' c ′ , listed in ascending order of the arrival time of the ( t − 1 ) (t-1) ( t − 1 ) -th vertex. If A i A_i A i and b j b_j b j share the same color in c ′ c' c ′ , we say that “A i A_i A i and b j b_j b j are matched”. Then, we define the following tuple ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) :
Z = { z 1 , … , z m } Z=\{z_1,\ldots,z_m\} Z = { z 1 , … , z m } (z 1 < ⋯ < z m z_1<\cdots<z_m z 1 < ⋯ < z m ): The set of indices such that each A z i A_{z_i} A z i matches to some b j b_j b j . Let π : [ m ] → [ m ] \pi:[m]\to[m] π : [ m ] → [ m ] be the (unique) permutation such that each A z i A_{z_i} A z i is matched to b π ( i ) b_{\pi(i)} b π ( i ) .
Q = ( q 1 , … , q m ) Q=(q_1,\ldots,q_m) Q = ( q 1 , … , q m ) : Each A z i A_{z_i} A z i is matched to a vertex of base color q i q_i q i , i.e., φ ( b π ( i ) ) = q i \varphi(b_{\pi(i)})=q_i φ ( b π ( i ) ) = q i .
R = ( r 1 , … , r m ) R=(r_1,\ldots,r_m) R = ( r 1 , … , r m ) : Each A z i A_{z_i} A z i is matched to the ( r i + 1 ) (r_i+1) ( r i + 1 ) -th last vertex with base color q i q_i q i among b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m that are not adjacent to any vertex in A z i A_{z_i} A z i . In other words,
r i : = ∣ { j ∈ { π ( i ) + 1 , … , m } : φ ( b j ) = q i , and b j is not adjacent to any vertex in A z i } ∣ . r_i:=\left|\left\{j\in\{\pi(i)+1,\ldots,m\}:\varphi(b_j)=q_i,\text{ and }b_j\text{ is not adjacent to any vertex in }A_{z_i}\right\}\right|. r i := ∣ { j ∈ { π ( i ) + 1 , … , m } : φ ( b j ) = q i , and b j is not adjacent to any vertex in A z i } ∣ .
We call ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) the “profile tuple” for the coloring c ′ ∈ C a l l c'\in\mathcal{C}_{\mathrm{all}} c ′ ∈ C all ; see Figure 13 for an illustration.
Figure 13. An example of the profile tuple ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) .
We group the colorings in C a l l \mathcal{C}_{\mathrm{all}} C all solely by the profile tuple. Specifically, we let Λ \Lambda Λ be the set of all possible profile tuples ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) , and for each λ = ( Z , Q , R ) ∈ Λ \lambda=(Z,Q,R)\in\Lambda λ = ( Z , Q , R ) ∈ Λ , we let C λ \mathcal{C}_{\lambda} C λ be the set of colorings in C a l l \mathcal{C}_{\mathrm{all}} C all such that the profile tuple is ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) . Then, each C λ \mathcal{C}_{\lambda} C λ is a good set, as proven below.
Lemma 5.10. For each λ = ( Z , Q , R ) ∈ Λ \lambda=(Z,Q,R)\in\Lambda λ = ( Z , Q , R ) ∈ Λ , C λ \mathcal{C}_{\lambda} C λ is a good set.
Proof. Suppose that C λ \mathcal{C}_{\lambda} C λ is not a good set, that is, there exists an i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } and a partial coloring c − : V ≺ b i → N c^{-}:V_{\prec b_i}\to\mathbb{N} c − : V ≺ b i → N that violates the condition in Definition 5.7. We give two important observations:
Let ℓ \ell ℓ be the number of colors that are used at least t − 1 t-1 t − 1 times in c − c^{-} c − . Then, A 1 , … , A ℓ A_1,\ldots,A_{\ell} A 1 , … , A ℓ is unchanged regardless of how we extend c − c^{-} c − to a coloring in C λ \mathcal{C}_{\lambda} C λ .
Also, each π ( j ) \pi(j) π ( j ) is uniquely determined by A z j A_{z_j} A z j , q j q_j q j , and r j r_j r j : indeed, b π ( j ) b_{\pi(j)} b π ( j ) is the ( r j + 1 ) (r_j+1) ( r j + 1 ) -th last vertex with base color q j q_j q j among b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m that are not adjacent to any vertex in A z j A_{z_j} A z j . Therefore, for j j j with z j ≤ ℓ z_j\le\ell z j ≤ ℓ , π ( j ) \pi(j) π ( j ) is unchanged regardless of how we extend c − c^{-} c − to a coloring in C λ \mathcal{C}_{\lambda} C λ .
Since it violates the condition in Definition 5.7, there are two (or more) possible choices for the color of b i b_i b i in the extensions of c − c^{-} c − . This means that for some j 1 , j 2 j_1,j_2 j 1 , j 2 (j 1 ≠ j 2 j_1\ne j_2 j 1 = j 2 , z j 1 , z j 2 ≤ ℓ z_{j_1},z_{j_2}\le\ell z j 1 , z j 2 ≤ ℓ ), both A z j 1 A_{z_{j_1}} A z j 1 and A z j 2 A_{z_{j_2}} A z j 2 can be matched to b i b_i b i . However, due to the observations above, π ( j 1 ) \pi(j_1) π ( j 1 ) and π ( j 2 ) \pi(j_2) π ( j 2 ) are unchanged across these extensions (i.e., uniquely determined by A z j A_{z_j} A z j , q j q_j q j , and r j r_j r j ), and therefore π ( j 1 ) = i \pi(j_1)=i π ( j 1 ) = i and π ( j 2 ) = i \pi(j_2)=i π ( j 2 ) = i hold at the same time. This contradicts that π \pi π is a permutation. Thus, C λ \mathcal{C}_{\lambda} C λ is a good set. □
Lemma 5.11. For each coloring c ′ ∈ C a l l c'\in\mathcal{C}_{\mathrm{all}} c ′ ∈ C all , its profile tuple ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) satisfies r 1 + ⋯ + r m ≤ ( θ t − 1 ) m r_1+\cdots+r_m\le(\theta_t-1)m r 1 + ⋯ + r m ≤ ( θ t − 1 ) m .
Proof. We count the number of pairs ( i , j ) (i,j) ( i , j ) such that (1) i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } , j ∈ { π ( i ) + 1 , … , m } j\in\{\pi(i)+1,\ldots,m\} j ∈ { π ( i ) + 1 , … , m } , (2) φ ( b j ) = q i \varphi(b_j)=q_i φ ( b j ) = q i , and (3) b j b_j b j is not adjacent to any vertex in A z i A_{z_i} A z i .
For each j j j , there are at most θ t − 1 \theta_t-1 θ t − 1 such pairs. The reason is as follows: for a counted pair ( i , j ) (i,j) ( i , j ) , vertex b j b_j b j is not adjacent to any vertex in A z i ∪ { b π ( i ) } A_{z_i}\cup\{b_{\pi(i)}\} A z i ∪ { b π ( i ) } , due to φ ( b j ) = φ ( b π ( i ) ) ( = q i ) \varphi(b_j)=\varphi(b_{\pi(i)}) (=q_i) φ ( b j ) = φ ( b π ( i ) ) ( = q i ) . Hence, if there are θ t \theta_t θ t such i i i ’s, then b j b_j b j should have become a level-( t + 1 ) (t+1) ( t + 1 ) or higher vertex, which contradicts c ′ ∈ C a l l c'\in\mathcal{C}_{\mathrm{all}} c ′ ∈ C all . Therefore, the total number of pairs is at most ( θ t − 1 ) m (\theta_t-1)m ( θ t − 1 ) m .
Therefore, r 1 + ⋯ + r m ≤ ( θ t − 1 ) m r_1+\cdots+r_m\le(\theta_t-1)m r 1 + ⋯ + r m ≤ ( θ t − 1 ) m . □
Lemma 5.12. The number of possible profile tuples ( Z , Q , R ) (Z,Q,R) ( Z , Q , R ) , i.e., ∣ Λ ∣ |\Lambda| ∣Λ∣ , is at most ( n m ) ⋅ k m ⋅ ( θ t m m ) \binom{n}{m}\cdot k^m\cdot\binom{\theta_t m}{m} ( m n ) ⋅ k m ⋅ ( m θ t m ) .
Proof. There are at most ( n m ) \binom{n}{m} ( m n ) possibilities for Z Z Z because it is a size-m m m subset of { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } . There are at most k m k^m k m possibilities for Q = ( q 1 , … , q m ) Q=(q_1,\ldots,q_m) Q = ( q 1 , … , q m ) because each q i q_i q i is chosen from { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } . For R = ( r 1 , … , r m ) R=(r_1,\ldots,r_m) R = ( r 1 , … , r m ) , we have r 1 + ⋯ + r m ≤ ( θ t − 1 ) m r_1+\cdots+r_m\le(\theta_t-1)m r 1 + ⋯ + r m ≤ ( θ t − 1 ) m by Lemma 5.11 . Hence, by the so-called “stars and bars” argument, there are at most ( θ t m m ) \binom{\theta_t m}{m} ( m θ t m ) possibilities for R R R . Therefore, Lemma 5.12 follows. □
Analysis Part II: Number of Colors Used
We are now ready to show an upper bound on the expected number of level-t t t colors. Then we estimate the number of colors used in Algorithm 2 with an optimal parameter setting.
Lemma 5.13. Let t ∈ { 2 , … , d − 1 } t \in\{2,\ldots,d-1\} t ∈ { 2 , … , d − 1 } . In the final state, the expected number of level-t t t colors is at most e 3 / 2 n 2 k θ t θ t − 1 + 2 e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}+2 e 3/2 n θ t − 1 2 k θ t + 2 .
Proof. Let X X X be the random variable that represents the final number of level-t t t colors. By Lemma 5.8, Lemma 5.10 , Lemma 5.12 , and that there are ( n m ) \binom{n}{m} ( m n ) combinations for b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m ,
Pr [ X = m ] = 1 θ t − 1 m ⋅ ( n m ) ⋅ k m ⋅ ( θ t m m ) ⋅ ( n m ) ≤ ( e 3 θ t k n 2 θ t − 1 m 2 ) m \Pr[X=m]=\frac{1}{\theta_{t-1}^{m}}\cdot\binom{n}{m}\cdot k^m\cdot\binom{\theta_t m}{m}\cdot\binom{n}{m}\leq\left(\frac{e^3\theta_tkn^2}{\theta_{t-1}m^2}\right)^m Pr [ X = m ] = θ t − 1 m 1 ⋅ ( m n ) ⋅ k m ⋅ ( m θ t m ) ⋅ ( m n ) ≤ ( θ t − 1 m 2 e 3 θ t k n 2 ) m
due to ( n m ) ≤ ( e n / m ) m \binom{n}{m}\leq(en/m)^m ( m n ) ≤ ( e n / m ) m and ( θ t m m ) ≤ ( e θ t ) m \binom{\theta_t m}{m}\leq(e\theta_t)^m ( m θ t m ) ≤ ( e θ t ) m . Since
e 3 θ t k n 2 θ t − 1 m 2 ≤ 1 2 \frac{e^3\theta_tkn^2}{\theta_{t-1}m^2}\leq\frac{1}{2} θ t − 1 m 2 e 3 θ t k n 2 ≤ 2 1
holds for all m ≥ e 3 / 2 n 2 k θ t θ t − 1 m\geq e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}} m ≥ e 3/2 n θ t − 1 2 k θ t , the probability that the number of level-t t t colors is exactly m m m is at most 1 / 2 m 1/2^m 1/ 2 m for all m ≥ e 3 / 2 n 2 k θ t θ t − 1 m\geq e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}} m ≥ e 3/2 n θ t − 1 2 k θ t . Therefore,
E [ X ] ≤ e 3 / 2 n 2 k θ t θ t − 1 + ∑ i = 1 ∞ ( i ⋅ 1 2 i ) = e 3 / 2 n 2 k θ t θ t − 1 + 2. \mathbb{E}[X]\leq e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}+\sum_{i=1}^{\infty}\left(i\cdot\frac{1}{2^i}\right)=e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}+2. E [ X ] ≤ e 3/2 n θ t − 1 2 k θ t + i = 1 ∑ ∞ ( i ⋅ 2 i 1 ) = e 3/2 n θ t − 1 2 k θ t + 2.
Lemma 5.14. The expected number of colors used in Algorithm 2 is at most
n d + 2 ( d − 2 ) + k θ 1 + ∑ t = 2 d − 1 e 3 / 2 n 2 k θ t θ t − 1 . \frac{n}{d}+2(d-2)+k\theta_1+\sum_{t=2}^{d-1}e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}. d n + 2 ( d − 2 ) + k θ 1 + t = 2 ∑ d − 1 e 3/2 n θ t − 1 2 k θ t .
Proof. If there are c t c_t c t level-t t t colors for each t = 1 , … , d − 1 t=1,\ldots,d-1 t = 1 , … , d − 1 , the expected total number of colors is
∑ t = 1 d − 1 E [ c t ] + 1 d ( n − ∑ t = 1 d − 1 ( t ⋅ E [ c t ] ) ) ≤ n d + ∑ t = 1 d − 1 E [ c t ] ≤ n d + k θ 1 + ∑ t = 2 d − 1 ( e 3 / 2 n 2 k θ t θ t − 1 + 2 ) . \begin{aligned}
\sum_{t=1}^{d-1}\mathbb{E}[c_t]+\frac{1}{d}\left(n-\sum_{t=1}^{d-1}(t\cdot\mathbb{E}[c_t])\right)\leq\frac{n}{d}+\sum_{t=1}^{d-1}\mathbb{E}[c_t] \\
&\leq\frac{n}{d}+k\theta_1+\sum_{t=2}^{d-1}\left(e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}+2\right).
\end{aligned} t = 1 ∑ d − 1 E [ c t ] + d 1 ( n − t = 1 ∑ d − 1 ( t ⋅ E [ c t ]) ) ≤ d n + t = 1 ∑ d − 1 E [ c t ] ≤ d n + k θ 1 + t = 2 ∑ d − 1 ( e 3/2 n θ t − 1 2 k θ t + 2 ) .
where the last inequality is due to Lemma 5.6 and Lemma 5.13 .
Theorem 5.15. Let d ≥ 2 d\geq2 d ≥ 2 be an integer. Algorithm 2 uses at most n / d + 11 d n ( 2 d − 4 ) / ( 2 d − 3 ) k ( d − 1 ) / ( 2 d − 3 ) n/d+11d n^{(2d-4)/(2d-3)}k^{(d-1)/(2d-3)} n / d + 11 d n ( 2 d − 4 ) / ( 2 d − 3 ) k ( d − 1 ) / ( 2 d − 3 ) colors in expectation for an n n n -vertex k k k -colorable graph, when n n n and k k k are known in advance, with an appropriate setting of parameters θ d − 1 , … , θ 2 , θ 1 \theta_{d-1},\ldots,\theta_2,\theta_1 θ d − 1 , … , θ 2 , θ 1 .
Proof. Consider setting the parameters to θ t = ⌊ ( n 2 / k ) ( d − t − 1 ) / ( 2 d − 3 ) ⌋ \theta_t=\left\lfloor(n^2/k)^{(d-t-1)/(2d-3)}\right\rfloor θ t = ⌊ ( n 2 / k ) ( d − t − 1 ) / ( 2 d − 3 ) ⌋ for each t ∈ { 1 , … , d − 1 } t\in\{1,\ldots,d-1\} t ∈ { 1 , … , d − 1 } . Let c c c be the random variable that represents the total number of colors Algorithm 2 used. Due to Lemma 5.14, the following holds:
E [ c ] ≤ n d + 2 ( d − 2 ) + k θ 1 + ∑ t = 2 d − 1 e 3 / 2 n 2 k θ t θ t − 1 ≤ n d + 2 ( d − 2 ) + k θ 1 + ∑ t = 2 d − 1 ( e 3 / 2 n ⋅ 2 n 1 2 d − 3 k d − 1 2 d − 3 ) ≤ n d + 2 ( d − 2 ) + n 2 d − 4 2 d − 3 k d − 1 2 d − 3 + 2 e 3 / 2 ∑ t = 2 d − 1 n 2 d − 4 2 d − 3 k d − 1 2 d − 3 ≤ n d + ( 2 e 3 / 2 + 2 ) ⋅ d n 2 d − 4 2 d − 3 k d − 1 2 d − 3 ≤ n d + 11 d n 2 d − 4 2 d − 3 k d − 1 2 d − 3 . \begin{aligned}
\mathbb{E}[c] &\le\frac{n}{d}+2(d-2)+k\theta_1+\sum_{t=2}^{d-1}e^{3/2}n\sqrt{\frac{2k\theta_t}{\theta_{t-1}}}\\
&\le\frac{n}{d}+2(d-2)+k\theta_1+\sum_{t=2}^{d-1}\left(e^{3/2}n\cdot2n^{\frac{1}{2d-3}}k^{\frac{d-1}{2d-3}}\right)\\
&\le\frac{n}{d}+2(d-2)+n^{\frac{2d-4}{2d-3}}k^{\frac{d-1}{2d-3}}+2e^{3/2}\sum_{t=2}^{d-1}n^{\frac{2d-4}{2d-3}}k^{\frac{d-1}{2d-3}}\\
&\le\frac{n}{d}+(2e^{3/2}+2)\cdot dn^{\frac{2d-4}{2d-3}}k^{\frac{d-1}{2d-3}}\\
&\le\frac{n}{d}+11dn^{\frac{2d-4}{2d-3}}k^{\frac{d-1}{2d-3}}.
\end{aligned} E [ c ] ≤ d n + 2 ( d − 2 ) + k θ 1 + t = 2 ∑ d − 1 e 3/2 n θ t − 1 2 k θ t ≤ d n + 2 ( d − 2 ) + k θ 1 + t = 2 ∑ d − 1 ( e 3/2 n ⋅ 2 n 2 d − 3 1 k 2 d − 3 d − 1 ) ≤ d n + 2 ( d − 2 ) + n 2 d − 3 2 d − 4 k 2 d − 3 d − 1 + 2 e 3/2 t = 2 ∑ d − 1 n 2 d − 3 2 d − 4 k 2 d − 3 d − 1 ≤ d n + ( 2 e 3/2 + 2 ) ⋅ d n 2 d − 3 2 d − 4 k 2 d − 3 d − 1 ≤ d n + 11 d n 2 d − 3 2 d − 4 k 2 d − 3 d − 1 .
We highlight each term with different colors for clarity. Note that the second inequality holds due to θ t ′ / θ t ≤ 2 \theta'_t/\theta_t\le2 θ t ′ / θ t ≤ 2 when θ t ′ \theta'_t θ t ′ is a real number that removes the floor function from θ t \theta_t θ t . □
The Competitive Ratio
Theorem 5.15 obtains an algorithm with a non-trivial performance guarantee for graphs with large chromatic number k k k . On the other hand, in 1997, Halldórsson [16 ] presented a randomized online coloring algorithm for graphs with small k k k , summarized as follows.
Theorem 5.16 ([16 ] ). There is a polynomial-time randomized online coloring algorithm for k k k -colorable graphs such that the expected number of colors used is at most $39n^{(k-2)/(k-1)}(\log n)^{1/(k-1)}f o r a n y for any f or an y k\ge 2.
Combining our main result with Theorem 5.16, we obtain the desired O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) -competitive randomized algorithm as follows.
Theorem 1.2. There exists a polynomial-time randomized online coloring algorithm, against an oblivious adversary, that attains a competitive ratio of O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) .
Proof. Let α = log n 2 log log n \alpha=\frac{\log n}{2\log\log n} α = 2 l o g l o g n l o g n . First, by applying Theorem 5.15 with d = max ( ⌈ log n / ( 6 log log n ) ⌉ , 2 ) d=\max(\lceil\log n/(6\log\log n)\rceil,2) d = max (⌈ log n / ( 6 log log n )⌉ , 2 ) , there exists an algorithm that uses at most
n d + 11 d n 1 − 1 2 d − 3 ⋅ k ≤ 6 n log log n log n + O ( log n log log n ⋅ n log 3 n ) ⋅ k (2) \frac{n}{d}+11dn^{1-\frac{1}{2d-3}}\cdot k\le\frac{6n\log\log n}{\log n}+O\left(\frac{\log n}{\log\log n}\cdot\frac{n}{\log^3 n}\right)\cdot k \tag*{(2)} d n + 11 d n 1 − 2 d − 3 1 ⋅ k ≤ log n 6 n log log n + O ( log log n log n ⋅ log 3 n n ) ⋅ k (2)
when both n n n and k k k are known in advance. This implies that (a) for α < k \alpha<k α < k , there is an algorithm that uses O ( n ( log log n ) 2 / log 2 n ) ⋅ k O(n(\log\log n)^2/\log^2 n)\cdot k O ( n ( log log n ) 2 / log 2 n ) ⋅ k colors. (b) Second, by Theorem 5.16, for 2 ≤ k ≤ α 2\le k\le\alpha 2 ≤ k ≤ α , there exists an algorithm that uses O ( n / log 2 n ) O(n/\log^2 n) O ( n / log 2 n ) colors. (c) Third, for k = 1 k=1 k = 1 , there exists an algorithm that uses one color. Applying Lemma 3.3 for (a)–(c), we obtain an O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) -competitive algorithm. Finally, this runs in polynomial time, since both Theorem 5.15 and Theorem 5.16 run in polynomial time and n ( log log n ) 2 / log 2 n ≥ n 1 / 100 n(\log\log n)^2/\log^2 n\ge n^{1/100} n ( log log n ) 2 / log 2 n ≥ n 1/100 (which is required to apply Lemma 3.3). □
The Upper Bound for Deterministic Algorithms
In this section, we present a deterministic online coloring algorithm that attains a competitive ratio of O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) , for an arbitrary fixed ε \varepsilon ε (0 < ε < 2 0 < \varepsilon< 2 0 < ε < 2 ).
Proof framework. In the main problem, we consider online coloring for N N N -vertex graphs. The following parameters are used throughout this section:
M : = ⌈ ( log log N ) 1 − ε / 2 ⌉ , L : = ⌈ N 1 / M 11 ⌉ . M := \left\lceil(\log\log N)^{1-\varepsilon/2}\right\rceil,\qquad L := \left\lceil N^{1/M^{11}}\right\rceil. M := ⌈ ( log log N ) 1 − ε /2 ⌉ , L := ⌈ N 1/ M 11 ⌉ .
The goal of the entire section is to develop a deterministic algorithm that colors N N N -vertex M 2 M^2 M 2 -colorable graphs using O ( N / M ) O(N/M) O ( N / M ) colors, where N N N is known in advance. In the analysis, we always assume that N N N is sufficiently large . Note that this means M M M and L L L are also sufficiently large.
This suffices to prove the desired competitive ratio of O ( N / M 2 ) O(N/M^2) O ( N / M 2 ) because of Lemma 3.3 and the fact that Kawarabayashi, Yoneda, and Yoneda’s algorithm [23 ] already colors M M M -colorable graphs using O ( N / M 2 ) O(N/M^2) O ( N / M 2 ) colors, as we discuss in Subsection 6.12 (note that we use uppercase N N N to distinguish it from n n n , the number of vertices in “subproblems” we discuss in later subsections, which is often unknown). This section is divided into three parts.
Part A. First, we construct a deterministic online algorithm that colors L L L -vertex ( M + 1 ) (M + 1) ( M + 1 ) -clique-free graphs using at most L / M L/M L / M colors. Note that this improves upon the best-known algorithm by Bradač et al. [BFS+26]. We discuss this in Subsection 6.1 and Subsection 6.2.
Part B. Then, we present a new technical framework that adapts the algorithm for clique-free graphs to the framework of [23 ] , and show that M 2 M^2 M 2 -colorable graphs can be colored online with O ( N / M ) O(N/M) O ( N / M ) colors. Subsection 6.3 gives an overview of the idea, and Subsection 6.4 through Subsection 6.11 present the algorithm and its analysis.
Part C. Finally, we prove a competitive ratio of O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) in Subsection 6.12.
Clique-Free Algorithm Part I: Online Object Coloring
In this subsection, we define a novel problem, online object coloring , which serves as a key tool in our clique-free algorithm. (A similar idea also appears in the work of Bradač et al. [BFS+26].)
Definition 6.1 (Online Object Coloring). There is a finite non-empty ground set U U U . In the online object coloring problem, the sets A 1 , … , A n ⊆ U A_1,\ldots,A_n \subseteq U A 1 , … , A n ⊆ U arrive sequentially. When A i A_i A i arrives, we must immediately assign a color to it, so that the following requirement is satisfied:
Requirement: For each color c c c assigned to at least one set, the sets with color c c c must have a common element. In other words, ⋂ i ∈ T ( c ) A i ≠ ∅ \bigcap_{i\in T(c)} A_i \ne\varnothing ⋂ i ∈ T ( c ) A i = ∅ must hold, where T ( c ) T(c) T ( c ) is the set of indices i i i for which color c c c is assigned to the set A i A_i A i .
This problem specifies a real parameter μ ≥ 1 \mu\ge1 μ ≥ 1 that is known from the beginning. It is guaranteed that ∣ A i ∣ ≥ ∣ U ∣ / μ |A_i| \ge|U|/\mu ∣ A i ∣ ≥ ∣ U ∣/ μ for each i i i . Note that n n n is not known in advance. The goal is to minimize the number of colors used. We assume that the ground set U U U is not known in advance; see Remark 6.2 for clarification.
Remark 6.2. We assume that the ground set U U U , or even its size ∣ U ∣ |U| ∣ U ∣ , is not known in advance. This means that an online object coloring algorithm can only “see” the elements in U U U that belong to the sets A 1 , … , A i A_1,\ldots,A_i A 1 , … , A i that have already arrived. Since the parameter μ ≥ 1 \mu\ge1 μ ≥ 1 is known to the algorithm, the algorithm also knows that ∣ A i ∣ ≥ ∣ U ∣ / μ |A_i| \ge|U|/\mu ∣ A i ∣ ≥ ∣ U ∣/ μ holds (which also implies that ∣ A i ∣ ≥ ∣ A 1 ∪ ⋯ ∪ A n ∣ / μ |A_i| \ge|A_1 \cup\cdots\cup A_n|/\mu ∣ A i ∣ ≥ ∣ A 1 ∪ ⋯ ∪ A n ∣/ μ will definitely hold).
Consequently, for a “parent” algorithm that uses online object coloring as a subroutine (such as Algorithm 4), it is not required to specify U U U from the beginning, because an online object coloring algorithm cannot use information about U U U . Hence, it is possible for the parent algorithm to specify the sets A 1 , A 2 , … A_1,A_2,\ldots A 1 , A 2 , … online, and finally fix U = A 1 ∪ ⋯ ∪ A n U = A_1 \cup\cdots\cup A_n U = A 1 ∪ ⋯ ∪ A n only for the purpose of analysis. This is valid as long as ∣ A i ∣ ≥ ∣ U ∣ / μ |A_i| \ge|U|/\mu ∣ A i ∣ ≥ ∣ U ∣/ μ holds for every i i i .
Lemma 6.3. Let μ ≥ 1 \mu\ge1 μ ≥ 1 be a real number. There exists a deterministic algorithm for online object coloring with parameter μ \mu μ such that the number of colors used is at most
min h ∈ { 1 , 2 , 3 , … } { n h + ( 2 μ ) h − 1 } . \min_{h \in\{1,2,3,\ldots\}} \left\{\frac{n}{h} + (2\mu)^{h-1}\right\}. h ∈ { 1 , 2 , 3 , … } min { h n + ( 2 μ ) h − 1 } .
Proof. Consider the following algorithm. We maintain a list of sets X 1 , … , X t X_1,\ldots,X_t X 1 , … , X t ; initially t = 0 t=0 t = 0 . When a new set A i A_i A i arrives, we perform the following steps:
If there exists c ∈ { 1 , … , t } c \in\{1,\ldots,t\} c ∈ { 1 , … , t } such that ∣ X c ∩ A i ∣ ≥ ∣ X c ∣ / ( 2 μ ) |X_c \cap A_i| \ge|X_c|/(2\mu) ∣ X c ∩ A i ∣ ≥ ∣ X c ∣/ ( 2 μ ) , then we choose any such c c c and assign color c c c to the set A i A_i A i . We then update X c ← X c ∩ A i X_c \leftarrow X_c \cap A_i X c ← X c ∩ A i .
Otherwise, we assign color t + 1 t+1 t + 1 to the set A i A_i A i . Then, we set X t + 1 ← A i ∖ ( X 1 ∪ ⋯ ∪ X t ) X_{t+1} \leftarrow A_i \setminus(X_1 \cup\cdots\cup X_t) X t + 1 ← A i ∖ ( X 1 ∪ ⋯ ∪ X t ) and update t ← t + 1 t \leftarrow t+1 t ← t + 1 .
The pseudocode of this algorithm is given in Algorithm 3. It is easy to see that the sets X 1 , … , X t X_1,\ldots,X_t X 1 , … , X t are disjoint. The coloring satisfies the requirement, because for each color c ∈ { 1 , … , t } c \in\{1,\ldots,t\} c ∈ { 1 , … , t } , the set X c X_c X c is a subset of “the intersection of all sets A i A_i A i with color c c c ”, and X c X_c X c will not be empty. When Case (1) occurs, the size of the set X c X_c X c decreases by a factor of at most 2 μ 2\mu 2 μ . When Case (2) occurs, we can lower bound the size of the new set X t + 1 X_{t+1} X t + 1 as follows:
∣ X t + 1 ∣ = ∣ A i ∣ − ∑ c = 1 t ∣ X c ∩ A i ∣ ≥ ∣ A i ∣ − 1 2 μ ∑ c = 1 t ∣ X c ∣ ≥ ∣ U ∣ μ − ∣ U ∣ 2 μ = ∣ U ∣ 2 μ . |X_{t+1}| = |A_i| - \sum_{c=1}^{t} |X_c \cap A_i| \ge|A_i| - \frac{1}{2\mu}\sum_{c=1}^{t}|X_c| \ge\frac{|U|}{\mu} - \frac{|U|}{2\mu} = \frac{|U|}{2\mu}. ∣ X t + 1 ∣ = ∣ A i ∣ − c = 1 ∑ t ∣ X c ∩ A i ∣ ≥ ∣ A i ∣ − 2 μ 1 c = 1 ∑ t ∣ X c ∣ ≥ μ ∣ U ∣ − 2 μ ∣ U ∣ = 2 μ ∣ U ∣ .
Algorithm 3 An algorithm for online object coloring.
1: t ← 0
2: for each arrival of a set A_i do
3: if there exists c ∈ {1, . . . , t} such that |X_c ∩ A_i| ≥ |X_c|/(2μ) then
4: Assign color c to the set A_i
5: X_c ← X_c ∩ A_i
6: else
7: Assign color t + 1 to the set A_i
8: X_{t+1} ← A_i \ (X_1 ∪ · · · ∪ X_t)
9: t ← t + 1
Hence, for each color c c c , we have ∣ X c ∣ ≥ ∣ U ∣ / ( 2 μ ) ∣ T ( c ) ∣ |X_c| \ge|U|/(2\mu)^{|T(c)|} ∣ X c ∣ ≥ ∣ U ∣/ ( 2 μ ) ∣ T ( c ) ∣ , where T ( c ) T(c) T ( c ) is the set of indices i i i for which color c c c is assigned to the set A i A_i A i . Therefore, for any integer h ≥ 1 h \ge1 h ≥ 1 , the number of colors c c c with ∣ T ( c ) ∣ ≤ h − 1 |T(c)| \le h-1 ∣ T ( c ) ∣ ≤ h − 1 is at most ( 2 μ ) h − 1 (2\mu)^{h-1} ( 2 μ ) h − 1 , because such colors c c c satisfy ∣ X c ∣ ≥ ∣ U ∣ / ( 2 μ ) h − 1 |X_c| \ge|U|/(2\mu)^{h-1} ∣ X c ∣ ≥ ∣ U ∣/ ( 2 μ ) h − 1 . Also, the number of colors c c c with ∣ T ( c ) ∣ ≥ h |T(c)| \ge h ∣ T ( c ) ∣ ≥ h is at most n / h n/h n / h . Therefore, Lemma 6.3 follows.
Clique-Free Algorithm Part II: Main
We now solve the problem of coloring r r r -clique-free graphs online, denoted by CliqueFree( r ) (r) ( r ) . In particular, we show the following lemma.
Lemma 6.4. Let A ≥ 1 A \ge1 A ≥ 1 be a (fixed) integer parameter. Define the sequence n 2 , n 3 , … n_2,n_3,\ldots n 2 , n 3 , … as follows:
n 2 = A , n r = 3 A ⋅ { 6 r ( n r − 1 ) r − 1 } 3 A ( r = 3 , 4 , … ) n_2 = A,\qquad n_r = 3A \cdot\left\{6r(n_{r-1})^{r-1}\right\}^{3A}\quad(r = 3,4,\ldots) n 2 = A , n r = 3 A ⋅ { 6 r ( n r − 1 ) r − 1 } 3 A ( r = 3 , 4 , … ) Then, for every r ∈ { 2 , 3 , … } r \in\{2,3,\ldots\} r ∈ { 2 , 3 , … } , there exists a deterministic algorithm for CliqueFree( r ) (r) ( r ) on n r n_r n r vertices that uses at most r − 1 A ⋅ n r \frac{r-1}{A}\cdot n_r A r − 1 ⋅ n r colors.
We construct an algorithm by induction on r r r . For r = 2 r=2 r = 2 , the graph has no edges, so we color all vertices with the same color. This meets the requirement for Lemma 6.4 because 1 A ⋅ n 2 = 1 \frac{1}{A}\cdot n_2=1 A 1 ⋅ n 2 = 1 . Below, we describe the algorithm for CliqueFree( r ) (r) ( r ) when r ≥ 3 r \ge3 r ≥ 3 ; its pseudocode is given in Algorithm 4.
Algorithm. First, we prepare bins B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … ( ⊆ V ) (\subseteq V) ( ⊆ V ) , initially empty. It is assumed that each B i B_i B i induces a ( r − 1 ) (r-1) ( r − 1 ) -clique-free subgraph and contains at most n r − 1 n_{r-1} n r − 1 vertices. Roughly speaking, the strategy is to assign each vertex to a bin, and then color the vertices of each B i B_i B i using our algorithm for CliqueFree( r − 1 ) (r-1) ( r − 1 ) (defined by the induction hypothesis) because of this assumption. We use disjoint colors for different bins.
When a new vertex v v v arrives, we try to put v v v into a bin. Precisely, we compute the smallest j j j such that ∣ B j ∣ < n r − 1 |B_j|<n_{r-1} ∣ B j ∣ < n r − 1 and G [ B j ∪ { v } ] G[B_j\cup\{v\}] G [ B j ∪ { v }] is ( r − 1 ) (r-1) ( r − 1 ) -clique-free, and try to put v v v into B j B_j B j . However, this
Algorithm 4 CliqueFree( r ) (r) ( r ) : A recursive algorithm to color an n r n_r n r -vertex r r r -clique-free graph online, using the object coloring procedure.
Initiate an instance of online object coloring with parameter μ = 3 r ⋅ ( n r − 1 ) r − 1 \mu=3r\cdot(n_{r-1})^{r-1} μ = 3 r ⋅ ( n r − 1 ) r − 1
B 1 , B 2 , … ← ∅ B_1,B_2,\ldots\leftarrow\varnothing B 1 , B 2 , … ← ∅
J ← n r / ( 3 r ⋅ n r − 1 ) J\leftarrow n_r/(3r\cdot n_{r-1}) J ← n r / ( 3 r ⋅ n r − 1 )
for each arrival of a vertex v v v do
j ← \quad j\leftarrow j ← the smallest j j j such that ∣ B j ∣ < n r − 1 |B_j|<n_{r-1} ∣ B j ∣ < n r − 1 and G [ B j ∪ { v } ] G[B_j\cup\{v\}] G [ B j ∪ { v }] is ( r − 1 ) (r-1) ( r − 1 ) -clique-free
\quad if B j = ∅ B_j=\varnothing B j = ∅ and ∣ { ℓ : 1 ≤ ∣ B ℓ ∣ < n r − 1 } ∣ = J |\{\ell:1\le|B_\ell|<n_{r-1}\}|=J ∣ { ℓ : 1 ≤ ∣ B ℓ ∣ < n r − 1 } ∣ = J then
B ← B 1 ∪ ⋯ ∪ B j − 1 \qquad B\leftarrow B_1\cup\cdots\cup B_{j-1} B ← B 1 ∪ ⋯ ∪ B j − 1 (the set of vertices contained in any bin)
\qquad Present the set CLIQUE( N B ( v ) ) (N_B(v)) ( N B ( v )) to online object coloring
\qquad Color v v v with the color assigned to this set in online object coloring
\quad else
B j ← B j ∪ { v } \qquad B_j\leftarrow B_j\cup\{v\} B j ← B j ∪ { v }
\qquad Color v v v with the instance of CliqueFree( r − 1 ) (r-1) ( r − 1 ) created for B j B_j B j
approach might cause many “small” bins and exceed the limit of r − 1 A ⋅ n r \frac{r-1}{A}\cdot n_r A r − 1 ⋅ n r colors. Therefore, we let
J : = n r 3 r ⋅ n r − 1 , J := \frac{n_r}{3r\cdot n_{r-1}}, J := 3 r ⋅ n r − 1 n r ,
require that the number of “incomplete” bins (i.e., bins of size between 1 and n r − 1 − 1 n_{r-1}-1 n r − 1 − 1 ) should be at most J J J (note that J J J is an integer). Hence, if B j B_j B j is empty and there are J J J incomplete bins, then we do not put v v v into any bin. The good news is that, in this case, there are many ( r − 2 ) (r-2) ( r − 2 ) -cliques whose vertices are all adjacent to v v v (such a situation is illustrated in Figure 14 , left). Indeed, each incomplete bin B j B_j B j contains at least one such ( r − 2 ) (r-2) ( r − 2 ) -clique because v v v was not added to the bin B j B_j B j . Thus, across all bins, there are at least J J J such ( r − 2 ) (r-2) ( r − 2 ) -cliques. We color such vertices v v v by exploiting this property, as described below.
Figure 14. (Left) An example in which a vertex v v v cannot be put into any bin when r = 5 r = 5 r = 5 . (Right) An illustration of two vertices v 1 , v 2 v_1, v_2 v 1 , v 2 outside the bins that are assigned the same color. If there were an edge between v 1 v_1 v 1 and v 2 v_2 v 2 , this would contradict the fact that the entire graph is r r r -clique-free, since there must be at least one common clique.
Coloring outside bins. We denote by CLIQUE ( S ) \operatorname{CLIQUE}(S) CLIQUE ( S ) the set of ( r − 2 ) (r-2) ( r − 2 ) -cliques contained in S ⊆ V S \subseteq V S ⊆ V whose vertices all belong to the same bin. Let B : = B 1 ∪ ⋯ ∪ B j − 1 B := B_1 \cup\cdots\cup B_{j-1} B := B 1 ∪ ⋯ ∪ B j − 1 be the set of vertices contained in any bin. We then present the set CLIQUE ( N B ( v ) ) \operatorname{CLIQUE}(N_B(v)) CLIQUE ( N B ( v )) to online object coloring (as an input), and color v v v with the color assigned to this set in online object coloring.
Technically, we consider an instance of online object coloring where the ground set U U U is the “final” set of ( r − 2 ) (r-2) ( r − 2 ) -cliques whose vertices all belong to the same bin. (Some readers may wonder if this is valid in the online setting, but this is justified in Remark 6.2.)
For the parameter μ \mu μ in online object coloring, since each set has size at least J J J and we have ∣ U ∣ ≤ n r ⋅ ( n r − 1 ) r − 2 |U| \le n_r\cdot(n_{r-1})^{r-2} ∣ U ∣ ≤ n r ⋅ ( n r − 1 ) r − 2 (because there are at most n r n_r n r bins), we can set
μ = 3 r ⋅ ( n r − 1 ) r − 1 ( = n r ⋅ ( n r − 1 ) r − 2 J ) . \mu= 3r\cdot(n_{r-1})^{r-1}\left(=\frac{n_r\cdot(n_{r-1})^{r-2}}{J}\right). μ = 3 r ⋅ ( n r − 1 ) r − 1 ( = J n r ⋅ ( n r − 1 ) r − 2 ) .
This algorithm still gives a proper coloring. Indeed, for any two vertices v 1 , v 2 v_1,v_2 v 1 , v 2 (v 1 ≠ v 2 v_1\ne v_2 v 1 = v 2 ) assigned the same color in online object coloring, there is an ( r − 2 ) (r-2) ( r − 2 ) -clique S ⊆ V S\subseteq V S ⊆ V that belongs to both CLIQUE ( N B ( v 1 ) ) \operatorname{CLIQUE}(N_B(v_1)) CLIQUE ( N B ( v 1 )) and CLIQUE ( N B ( v 2 ) ) \operatorname{CLIQUE}(N_B(v_2)) CLIQUE ( N B ( v 2 )) , because of the requirement in Definition 6.1 . If there were an edge between v 1 v_1 v 1 and v 2 v_2 v 2 , then S ∪ { v 1 , v 2 } S\cup\{v_1,v_2\} S ∪ { v 1 , v 2 } would form an r r r -clique, contradicting the fact that the graph is r r r -clique-free (Figure 14 , right).
Analysis. Next, we analyze the number of colors used in Algorithm 4.
Proof of Lemma 6.4 . By the induction hypothesis, each bin uses at most r − 2 A ⋅ n r − 1 \frac{r-2}{A}\cdot n_{r-1} A r − 2 ⋅ n r − 1 colors. Since there are at most n r n r − 1 + J \frac{n_r}{n_{r-1}}+J n r − 1 n r + J bins, the number of colors used across all bins is at most
r − 2 A ⋅ n r − 1 ⋅ ( n r n r − 1 + J ) = r − 2 A ⋅ n r + r − 2 A ⋅ n r − 1 ⋅ n r 3 r ⋅ n r − 1 ≤ r − 2 A ⋅ n r + 1 3 A ⋅ n r . \frac{r-2}{A}\cdot n_{r-1}\cdot\left(\frac{n_r}{n_{r-1}}+J\right)
= \frac{r-2}{A}\cdot n_r+\frac{r-2}{A}\cdot n_{r-1}\cdot\frac{n_r}{3r\cdot n_{r-1}}
\le\frac{r-2}{A}\cdot n_r+\frac{1}{3A}\cdot n_r. A r − 2 ⋅ n r − 1 ⋅ ( n r − 1 n r + J ) = A r − 2 ⋅ n r + A r − 2 ⋅ n r − 1 ⋅ 3 r ⋅ n r − 1 n r ≤ A r − 2 ⋅ n r + 3 A 1 ⋅ n r .
For online object coloring, by Lemma 6.3 (with h = 3 A h=3A h = 3 A ), the number of colors used is at most
n r 3 A + ( 2 μ ) 3 A = n r 3 A + { 6 r ⋅ ( n r − 1 ) r − 1 } 3 A = 1 3 A ⋅ n r + 1 3 A ⋅ n r . \frac{n_r}{3A}+(2\mu)^{3A}
= \frac{n_r}{3A}+\left\{6r\cdot(n_{r-1})^{r-1}\right\}^{3A}
= \frac{1}{3A}\cdot n_r+\frac{1}{3A}\cdot n_r. 3 A n r + ( 2 μ ) 3 A = 3 A n r + { 6 r ⋅ ( n r − 1 ) r − 1 } 3 A = 3 A 1 ⋅ n r + 3 A 1 ⋅ n r .
Therefore, we use at most r − 2 A ⋅ n r + ( 1 3 A + 1 3 A + 1 3 A ) ⋅ n r = r − 1 A ⋅ n r \frac{r-2}{A}\cdot n_r+\left(\frac{1}{3A}+\frac{1}{3A}+\frac{1}{3A}\right)\cdot n_r=\frac{r-1}{A}\cdot n_r A r − 2 ⋅ n r + ( 3 A 1 + 3 A 1 + 3 A 1 ) ⋅ n r = A r − 1 ⋅ n r colors in total. □ \square □
Lemma 6.5. For every r ≥ 2 r \ge2 r ≥ 2 , we have n r ≤ ( 7 A ) ( 3 A ) r − 2 ( r − 1 ) ! n_r \le(7A)^{(3A)^{r-2}(r-1)!} n r ≤ ( 7 A ) ( 3 A ) r − 2 ( r − 1 )! .
Proof. By definition of n r n_r n r , we have log n r = 3 A ( r − 1 ) log n r − 1 + { 3 A log ( 6 r ) + log ( 3 A ) } \log n_r = 3A(r - 1)\log n_{r-1} + \{3A\log(6r) + \log(3A)\} log n r = 3 A ( r − 1 ) log n r − 1 + { 3 A log ( 6 r ) + log ( 3 A )} . Therefore, when we define M r : = ( 3 A ) r − 2 ( r − 1 ) ! M_r := (3A)^{r-2}(r-1)! M r := ( 3 A ) r − 2 ( r − 1 )! , we have
log n r M r = log n r − 1 M r − 1 + 3 A log ( 6 r ) + log ( 3 A ) M r . \frac{\log n_r}{M_r} = \frac{\log n_{r-1}}{M_{r-1}} + \frac{3A\log(6r) + \log(3A)}{M_r}. M r log n r = M r − 1 log n r − 1 + M r 3 A log ( 6 r ) + log ( 3 A ) .
Therefore, given that n 2 = A n_2 = A n 2 = A and M 2 = 1 M_2 = 1 M 2 = 1 , the following holds:
log n r M r = log A + ∑ i = 3 r 3 A log ( 6 i ) + log ( 3 A ) ( 3 A ) i − 2 ( i − 1 ) ! ≤ log A + ∑ i = 3 ∞ 3 log ( 6 i ) + log 3 3 i − 2 ( i − 1 ) ! = log A + 2.6602 … ( ≤ log ( 7 A ) ) . \begin{aligned}
\frac{\log n_r}{M_r} &= \log A + \sum_{i=3}^{r} \frac{3A\log(6i) + \log(3A)}{(3A)^{i-2}(i-1)!} \\
&\le\log A + \sum_{i=3}^{\infty} \frac{3\log(6i) + \log3}{3^{i-2}(i-1)!} \\
&= \log A + 2.6602\ldots\;(\le\log(7A)).
\end{aligned} M r log n r = log A + i = 3 ∑ r ( 3 A ) i − 2 ( i − 1 )! 3 A log ( 6 i ) + log ( 3 A ) ≤ log A + i = 3 ∑ ∞ 3 i − 2 ( i − 1 )! 3 log ( 6 i ) + log 3 = log A + 2.6602 … ( ≤ log ( 7 A )) .
where the first equality is derived by assigning A = 1 A = 1 A = 1 because this is the worst case. Therefore, log n r = ( 3 A ) r − 2 ( r − 1 ) ! log ( 7 A ) \log n_r = (3A)^{r-2}(r - 1)!\log(7A) log n r = ( 3 A ) r − 2 ( r − 1 )! log ( 7 A ) , and hence Lemma 6.5 follows. □
Corollary 6.6. Assuming that N N N is large enough, there exists a deterministic online algorithm for CliqueFree( M + 1 ) (M + 1) ( M + 1 ) on L L L vertices that uses at most L / M L/M L / M colors.
Proof. Apply Lemma 6.4 with parameter A = 2 M 2 A = 2M^2 A = 2 M 2 ; we can process n M + 1 n_{M+1} n M + 1 vertices with Algorithm 4 for CliqueFree( M + 1 ) (M + 1) ( M + 1 ) using n M + 1 2 M 2 ⋅ M \frac{n_{M+1}}{2M^2}\cdot M 2 M 2 n M + 1 ⋅ M colors. Hence, if L ≥ n M + 1 L \ge n_{M+1} L ≥ n M + 1 , then we can color all vertices using
( n M + 1 2 M 2 ⋅ M ) ⋅ ⌊ L n M + 1 ⌋ = n M + 1 2 M ⋅ ⌊ L n M + 1 ⌋ ≤ L M \left(\frac{n_{M+1}}{2M^2}\cdot M\right)\cdot\left\lfloor\frac{L}{n_{M+1}}\right\rfloor= \frac{n_{M+1}}{2M}\cdot\left\lfloor\frac{L}{n_{M+1}}\right\rfloor\le\frac{L}{M} ( 2 M 2 n M + 1 ⋅ M ) ⋅ ⌊ n M + 1 L ⌋ = 2 M n M + 1 ⋅ ⌊ n M + 1 L ⌋ ≤ M L
colors. Now, we prove L ≥ n M + 1 L \ge n_{M+1} L ≥ n M + 1 . By Lemma 6.5, we have n M + 1 ≤ ( 14 M 2 ) ( 6 M 2 ) M − 1 M ! = 2 2 Θ ( M log M ) n_{M+1} \le(14M^2)^{(6M^2)^{M-1}M!} = 2^{2^{\Theta(M\log M)}} n M + 1 ≤ ( 14 M 2 ) ( 6 M 2 ) M − 1 M ! = 2 2 Θ ( M l o g M ) . With M = ⌊ ( log log N ) 1 − ε / 2 ⌋ M = \lfloor(\log\log N)^{1-\varepsilon/2}\rfloor M = ⌊( log log N ) 1 − ε /2 ⌋ , we have log log n M + 1 = Θ ( M log M ) = o ( log log N ) \log\log n_{M+1} = \Theta(M\log M) = o(\log\log N) log log n M + 1 = Θ ( M log M ) = o ( log log N ) , which is smaller than log log L = ( 1 − o ( 1 ) ) log log N \log\log L = (1-o(1))\log\log N log log L = ( 1 − o ( 1 )) log log N . Therefore, n M + 1 ≤ L n_{M+1} \le L n M + 1 ≤ L , and Corollary 6.6 follows. □
Key Idea: Shortening the KYY27 Recursion
From this subsection onward, we present an algorithm that colors M 2 M^2 M 2 -colorable graphs using O ( N / M ) O(N/M) O ( N / M ) colors. The core idea is to incorporate our novel algorithm for ( M + 1 ) (M + 1) ( M + 1 ) -clique-free graphs (Algorithm 4) into the framework of Kawarabayashi, Yoneda, and Yoneda [23 ] . They obtained an algorithm that, for every constant k ≥ 2 k \ge2 k ≥ 2 , colors k k k -colorable graphs using O ~ ( n 1 − 2 / ( k ( k − 1 ) ) ) \widetilde{O}(n^{1-2/(k(k-1))}) O ( n 1 − 2/ ( k ( k − 1 )) ) colors and achieves a competitive ratio of O ( n / log log n ) O(n/\log\log n) O ( n / log log n ) .
Kierstead’s method. We first describe the idea behind Kierstead’s algorithm [21 ] , which colors 3-colorable graphs with O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors (for sufficiently small c > 0 c > 0 c > 0 ) and is foundational to [23 ] ’s framework. We color each vertex v v v using First-Fit if it can be colored with one of the first n 1 − c n^{1-c} n 1 − c colors. If First-Fit cannot color v v v , then v v v has degree at least n 1 − c n^{1-c} n 1 − c , so we exploit this fact to color these vertices as follows.
Step 1. Let S S S be the set of vertices colored by First-Fit. For a fixed x ∈ V ∖ S x \in V \setminus S x ∈ V ∖ S , let L 1 : = N S ( x ) L_1 := N_S(x) L 1 := N S ( x ) . Then, in some 3-coloring of G G G , at most 2 colors appear in L 1 L_1 L 1 (Figure 7 , left).
Step 2. Additionally, for a fixed edge { y , z } \{y,z\} { y , z } where y , z ∈ V ∖ S y,z \in V \setminus S y , z ∈ V ∖ S , let L 2 , y : = N L 1 ( y ) L_{2,y} := N_{L_1}(y) L 2 , y := N L 1 ( y ) and L 2 , z : = N L 1 ( z ) L_{2,z} := N_{L_1}(z) L 2 , z := N L 1 ( z ) . Then, in some 3-coloring of G G G , either L 2 , y L_{2,y} L 2 , y or L 2 , z L_{2,z} L 2 , z is “monochromatic” (Figure 7 , right).5
Step 3. This means either G [ N ( L 2 , y ) ] G[N(L_{2,y})] G [ N ( L 2 , y )] or G [ N ( L 2 , z ) ] G[N(L_{2,z})] G [ N ( L 2 , z )] is 2-colorable (i.e., bipartite) and can be colored online using only O ( log n ) O(\log n) O ( log n ) colors by the algorithm of Lovász, Saks, and Trotter [25 ] .
Moreover, in favorable cases, both L 2 , y L_{2,y} L 2 , y and L 2 , z L_{2,z} L 2 , z are large (due to the large degree of each vertex in V ∖ S V \setminus S V ∖ S ), and hence many future vertices belong to N ( L 2 , y ) N(L_{2,y}) N ( L 2 , y ) or N ( L 2 , z ) N(L_{2,z}) N ( L 2 , z ) . This provides the intuition behind achieving a bound of O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors (although [21 ] used some additional ideas).
Figure 15. A sketch of Kierstead’s algorithm that colors 3-colorable graphs with O ( n 1 − c ) O(n^{1-c}) O ( n 1 − c ) colors.
The KYY27 framework. To generalize to k k k -colorable graphs for any k ≥ 3 k \ge3 k ≥ 3 , small subgraphs with large chromatic numbers play a crucial role. In the preceding example for 3-colorable graphs, we picked a vertex x x x (chromatic number 1) in Step 1 and an edge { y , z } \{y,z\} { y , z } (chromatic number 2) in Step 2. For 4-colorable graphs, we also need to consider subgraphs of chromatic number 3, such as odd cycles. However, the subgraphs must be small, because a large subgraph creates too many recursive branches. Indeed, in the 3-colorable case, we need only two branches, L 2 , y L_{2,y} L 2 , y and L 2 , z L_{2,z} L 2 , z , because { y , z } \{y,z\} { y , z } has size two. We create two branches because the algorithm does not know which of L 2 , y L_{2,y} L 2 , y and L 2 , z L_{2,z} L 2 , z is “the correct one” (that is, monochromatic in some 3-coloring).
To overcome this difficulty, [23 ] introduced an online coloring procedure called LOC(k k k ). This procedure must (i) color incoming vertices using a small number of colors, or (ii) terminate by returning a small subgraph X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) satisfying χ ( G [ X ] ) > k \chi(G[X]) > k χ ( G [ X ]) > k , called a certificate . The algorithm for LOC(k k k ) in [23 ] is constructed recursively using LOC(0), . . . , LOC(k − 1 k-1 k − 1 ), and the algorithmic framework is similar to that of the 3-colorable case (First-Fit + Steps 1–3).
Limitation. The reason why the competitive ratio is limited to O ( n / log log n ) O(n/\log\log n) O ( n / log log n ) exactly lies in this recursion structure. Let f k f_k f k be an upper bound on the size of the certificate returned by LOC(k k k ), e.g., f 0 = 1 f_0 = 1 f 0 = 1 (x x x in Step 1) and f 1 = 2 f_1 = 2 f 1 = 2 ({ y , z } \{y,z\} { y , z } in Step 2). In [23 ] , the bound is roughly f k ≈ f 0 × f 1 × ⋯ × f k − 1 f_k \approx f_0 \times f_1 \times\cdots\times f_{k-1} f k ≈ f 0 × f 1 × ⋯ × f k − 1 , due to the recursion toward LOC(0), . . . , LOC(k − 1 k-1 k − 1 ). Since f k f_k f k grows double-exponentially (i.e., exceeds n n n when k = Θ ( log log n ) k = \Theta(\log\log n) k = Θ ( log log n ) ), the coefficient in the bound on the number of colors used also grows double-exponentially, limiting the competitive ratio.
Our Improvement. Our key modification is to restrict the recursive calls for LOC(k k k ) to LOC(0), . . . , LOC(k − M k-M k − M ). This is made possible by our algorithm for (M + 1 M+1 M + 1 )-clique-free graphs. Consequently, the certificate size is roughly f k ≈ f 0 × ⋯ × f k − M f_k \approx f_0 \times\cdots\times f_{k-M} f k ≈ f 0 × ⋯ × f k − M , and f k = n o ( 1 ) f_k = n^{o(1)} f k = n o ( 1 ) at k = Θ ( ( log log n ) 2 − ε ) k = \Theta((\log\log n)^{2-\varepsilon}) k = Θ (( log log n ) 2 − ε ) .
In our algorithm, we begin with a technique similar to the clique-free algorithm in Algorithm 4, rather than First-Fit. We maintain many bins, and we try to place each arriving vertex into a bin while ensuring that each bin remains (M + 1 M+1 M + 1 )-clique-free (note that each bin can be colored efficiently by Corollary 6.6). If no bin is available, then v v v has a large clique degree , that is, v v v is adjacent to many M M M -cliques (Figure 16 left). For these vertices, we take a recursive strategy analogous to Steps 1–3, which utilizes small subgraphs of large chromatic numbers to iteratively restrict the colors allowed across a collection of cliques (note that, in Steps 1–3, we iteratively restrict the number of colors allowed for a set of vertices using the large degree, but this time we consider cliques).
Figure 16. Left: the situation in which v v v cannot be put in any bin. Right: the intuitive reason why the recursion stops at LOC(k − M k-M k − M ).
Indeed, this strategy is stronger than [23 ] . Let us define a vertex v v v to be completely adjacent to a clique S S S if v v v is adjacent to all vertices in S S S . Suppose that we have succeeded in restricting the allowed colors in a collection of M M M -cliques S 1 , … , S t S_1,\ldots,S_t S 1 , … , S t to M M M colors in some k k k -coloring of G G G ; in other words, all these cliques use the same M M M colors. Then, the set of future vertices that are completely adjacent to at least one of S 1 , … , S t S_1,\ldots,S_t S 1 , … , S t is (k − M k-M k − M )-colorable (Figure 16 right). This is the intuition for why our algorithm for LOC(k k k ) only recurses to LOC(0), . . . , LOC(k − M k-M k − M ).
Notation and Definitions
We begin a formal discussion of a deterministic online algorithm that colors M 2 M^2 M 2 -colorable graphs using O ( N / M ) O(N/M) O ( N / M ) colors. First, we present notation and definitions, followed by the “subproblems” that serve as subroutines for solving the main problem.
Notation and definitions. Let G = ( V , E ) G=(V,E) G = ( V , E ) be a graph. For v ∈ V v\in V v ∈ V and a clique S ⊆ V S\subseteq V S ⊆ V , we say that v v v is “completely adjacent” to S S S if the vertex v v v is adjacent to all vertices in S S S . A set of M M M -cliques S = { S 1 , S 2 , … } \mathcal{S}=\{S_1,S_2,\ldots\} S = { S 1 , S 2 , … } (S i ⊆ V S_i\subseteq V S i ⊆ V ) is called a “clique block”. For a clique block S = { S 1 , S 2 , … } \mathcal{S}=\{S_1,S_2,\ldots\} S = { S 1 , S 2 , … } , we define vert ( S ) : = ⋃ i S i \operatorname{vert}(\mathcal{S}):=\bigcup_i S_i vert ( S ) := ⋃ i S i for the set of vertices that belong to S \mathcal{S} S .
Locally k k k -colorable graph. Kawarabayashi, Yoneda, and Yoneda [23 ] introduced a notion of “locally k k k -colorable graph”: a graph that has no small non-k k k -colorable subgraph. In this paper, a graph G = ( V , E ) G=(V,E) G = ( V , E ) is locally k k k -colorable if χ ( G [ X ] ) ≤ k \chi(G[X])\leq k χ ( G [ X ]) ≤ k for all X ⊆ V X\subseteq V X ⊆ V with ∣ X ∣ ≤ f k |X|\leq f_k ∣ X ∣ ≤ f k , where the parameter f k f_k f k is a constant discussed in Subsection 6.10. They considered the following problem, LOC(k k k ), which stands for online coloring for locally k k k -colorable graphs.
Definition 6.8 (Problem LOC). Let k ≥ 0 k\geq0 k ≥ 0 be an integer. We define the problem LOC(k k k ) as follows: the online coloring problem in which, for each arrival of a vertex v v v , we must (i) color a vertex, and (ii) may then terminate by outputting a “certificate” that G G G is not locally k k k -colorable, that is, a set X ⊆ V X\subseteq V X ⊆ V such that ∣ X ∣ ≤ f k |X|\leq f_k ∣ X ∣ ≤ f k and χ ( G [ X ] ) > k \chi(G[X])>k χ ( G [ X ]) > k . Importantly, even if we terminate, we must color the last received vertex. We also define the problem LOC′ ( k ) ^\prime(k) ′ ( k ) to be the version of LOC(k k k ) where the final number of vertices n n n is known in advance.
The clique block subproblem. We define a subproblem that characterizes the recursive subroutine that, as mentioned in Subsection 6.3, is used “to iteratively restrict the colors allowed across a collection of cliques”. (Note that this can be viewed as an extension of “subproblem SP(k , ℓ , ν k,\ell,\nu k , ℓ , ν )” defined in [23 ] to the clique block setting, although we will not mention that here.)
Definition 6.9 (Problem CB). Let k , ℓ k,\ell k , ℓ be integers such that k ≥ ℓ ≥ M k\geq\ell\geq M k ≥ ℓ ≥ M , and let ν ≥ 1 \nu\geq1 ν ≥ 1 be a real parameter. We define problem CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) as follows. There is a fixed clique block S ≠ ∅ \mathcal{S}\neq\emptyset S = ∅ . Then, vertices are given one by one. For each vertex v v v , a set of cliques that are completely adjacent to v v v , denoted by C ( v ) \mathcal{C}(v) C ( v ) (⊆ S \subseteq\mathcal{S} ⊆ S ), is also given. It is guaranteed that ∣ C ( v ) ∣ ≥ ∣ S ∣ / ν |\mathcal{C}(v)|\geq|\mathcal{S}|/\nu ∣ C ( v ) ∣ ≥ ∣ S ∣/ ν . (Figure 17 , left). For each arrival of a vertex v v v , we must (i) color a vertex v v v , and (ii) may then terminate by outputting a pair ( S ′ , V ′ ) (\mathcal{S}^\prime,V^\prime) ( S ′ , V ′ ) (S ′ ⊆ S \mathcal{S}^\prime\subseteq\mathcal{S} S ′ ⊆ S , V ′ ⊆ V V^\prime\subseteq V V ′ ⊆ V ) that satisfies the following:
Condition: There exists no k k k -coloring of G [ vert ( S ′ ) ∪ V ′ ] G[\operatorname{vert}(\mathcal{S}^\prime)\cup V^\prime] G [ vert ( S ′ ) ∪ V ′ ] , φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] \varphi:(\operatorname{vert}(\mathcal{S}^\prime)\cup V^\prime)\to[k] φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] , such that ∣ { φ ( s ) : s ∈ vert ( S ′ ) } ∣ ≤ ℓ |\{\varphi(s):s\in\operatorname{vert}(\mathcal{S}^\prime)\}|\leq\ell ∣ { φ ( s ) : s ∈ vert ( S ′ )} ∣ ≤ ℓ (Figure 17 , right). In addition, ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ g k , ℓ |\operatorname{vert}(\mathcal{S}^\prime)\cup V^\prime|\leq g_{k,\ell} ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ g k , ℓ must hold, where the parameter g k , ℓ g_{k,\ell} g k , ℓ is a constant discussed in Subsection 6.10.
Figure 17. The input and output of the problem CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ).
Importantly, even if we terminate, we must color the last vertex. For convenience, we assume that the clique block S \mathcal{S} S is not known in advance , even though each C ( v ) \mathcal{C}(v) C ( v ) is given; see Remark 6.10 for clarification.
Remark 6.10. The assumption that the clique block S \mathcal{S} S , including its size ∣ S ∣ |\mathcal{S}| ∣ S ∣ , is unknown is similar to that of online object coloring (Definition 6.1 and Remark 6.2). This means that the algorithm for CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) can only “see” the elements in S \mathcal{S} S that appear in C ( v ) \mathcal{C}(v) C ( v ) for some vertex v v v that has already arrived. Consequently, for a “parent” algorithm that uses CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) as a subroutine, it is not required to specify S \mathcal{S} S from the beginning; it can specify the set of completely adjacent cliques for each arriving vertex, and finally fix S \mathcal{S} S to be the union of these sets only for the purpose of the analysis. See also Remark 6.2 for related details.
However, when we solve CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) for ℓ ∈ { M + 1 , … , k } \ell\in\{M+1,\ldots,k\} ℓ ∈ { M + 1 , … , k } (in Subsection 6.8), we initiate instances I I I for CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) , and here, we do fix a clique block S \mathcal{S} S upon initiating each such instance I I I (although we assume that this child instance does not know S \mathcal{S} S ). We denote the clique block for this instance by S ( I ) \mathcal{S}(I) S ( I ) .
Proof roadmap. We develop an algorithm to solve LOC ( M 2 ) \operatorname{LOC}(M^2) LOC ( M 2 ) using at most 3 N / M 3N/M 3 N / M colors. This suffices because LOC ( M 2 ) \operatorname{LOC}(M^2) LOC ( M 2 ) applies to M 2 M^2 M 2 -colorable graphs (as every M 2 M^2 M 2 -colorable graph is locally M 2 M^2 M 2 -colorable). Thus, we develop the algorithm by induction on k k k and ℓ \ell ℓ as follows.
Subsection 6.5: an algorithm to solve LOC ( k ) \operatorname{LOC}(k) LOC ( k ) using the algorithm for LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) .
Subsection 6.6: an algorithm to solve LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) using the algorithm for CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) (for some ν \nu ν ).
Subsection 6.7: an algorithm to solve CB ( k , M , ν ) \operatorname{CB}(k,M,\nu) CB ( k , M , ν ) using the algorithm for LOC ( k − M ) \operatorname{LOC}(k-M) LOC ( k − M ) . This serves as a kind of “base case” for the induction.
Subsection 6.8: an algorithm to solve CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) (ℓ ∈ { M + 1 , … , k } \ell\in\{M+1,\ldots,k\} ℓ ∈ { M + 1 , … , k } ) using the algorithms for CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) and LOC ( k − ℓ ) \operatorname{LOC}(k-\ell) LOC ( k − ℓ ) .
These four parts together constitute the overall algorithm. Its analysis is given in Subsection 6.9–Subsection 6.11. This roadmap is illustrated in Figure 18 .
Figure 18. The overall roadmap for solving LOC(k k k ). The recursive algorithm invokes LOC(0), … \ldots … , LOC(k − M k-M k − M ).
Algorithm for LOC(k k k )
First, we describe an algorithm to solve LOC ( k ) \operatorname{LOC}(k) LOC ( k ) where the final number of vertices n n n is unknown, using the algorithm for LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) where n n n is known in advance.
Algorithm. For t = 0 , 1 , … t=0,1,\ldots t = 0 , 1 , … , we process the next 2 t 2^t 2 t vertices (or until all vertices are used up) using the algorithm for LOC′ ( k ) '(k) ′ ( k ) with 2 t 2^t 2 t vertices. If LOC′ ( k ) '(k) ′ ( k ) returns a certificate X X X , then LOC(k k k ) immediately returns X X X . Note that we use disjoint colors for different instances of LOC′ ( k '(k ′ ( k ).
Observation. If the final number of vertices is n n n , then the final value of t t t equals ⌊ log 2 n ⌋ \lfloor\log_2 n \rfloor ⌊ log 2 n ⌋ . This implies that at most ⌊ log 2 n ⌋ + 1 \lfloor\log_2 n \rfloor+1 ⌊ log 2 n ⌋ + 1 instances of LOC′ ( k ) '(k) ′ ( k ) are created, and the specified number of vertices in each LOC′ ( k ) '(k) ′ ( k ) is at most 2 t ≤ n 2^t \le n 2 t ≤ n .
Algorithm for LOC′ ( k ) '(k) ′ ( k )
In this section, we describe an algorithm for LOC′ ( k ) '(k) ′ ( k ) , where the final number of vertices n n n is known in advance. The algorithm we describe below bears a substantial similarity to the clique-free algorithm (Algorithm 4).
k ≤ M k \le M k ≤ M case. We maintain bins B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … , and we put the i i i -th arriving vertex (i ≥ 1 i \ge1 i ≥ 1 ) into bin B b B_b B b where b = ⌈ i L ⌉ b=\left\lceil\frac{i}{L}\right\rceil b = ⌈ L i ⌉ . For each bin B b B_b B b , we use the algorithm for CliqueFree(M + 1 M+1 M + 1 ) given in Corollary 6.6. When a (M + 1 M+1 M + 1 )-clique appears in B b B_b B b , we output such a clique as a certificate and terminate. Note that we use one extra color to color the last received vertex.
k > M k > M k > M case. First, we prepare bins B 1 , B 2 , … B_1,B_2,\ldots B 1 , B 2 , … , initially empty. It is assumed that each B i B_i B i is (M + 1 M+1 M + 1 )-clique-free and contains at most L L L vertices. For each bin, we use the algorithm for CliqueFree(M + 1 M+1 M + 1 ) given in Corollary 6.6, using disjoint colors for different bins. In addition, we initiate a single instance of CB(k , k , ν k,k,\nu k , k , ν ), which uses colors disjoint from those used in the bins, where
J : = max { 1 , ⌈ n max ( L , n 1 / k ) ⌉ } , ν = 2 n ⋅ L M − 1 J J := \max\left\{1,\left\lceil\frac{n}{\max(L,n^{1/k})}\right\rceil\right\}, \qquad\nu=\frac{2n\cdot L^{M-1}}{J} J := max { 1 , ⌈ max ( L , n 1/ k ) n ⌉ } , ν = J 2 n ⋅ L M − 1
and its clique block S \mathcal{S} S is the “final” set of all M M M -cliques whose vertices all belong to the same bin. (Some readers may wonder if this is valid in the online setting, but this is justified in Remark 6.10).
Processing each vertex. The pseudocode for the algorithm is given in Algorithm 5. When a new vertex v v v arrives, we try to put v v v into a bin. Specifically, we compute the smallest j j j such that $\lvert B_j\rvert < L
Algorithm 5 An algorithm for LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) when k > M k > M k > M
B 1 , B 2 , ⋯ ← ∅ B_1, B_2, \cdots\leftarrow\emptyset B 1 , B 2 , ⋯ ← ∅
J ← max { 1 , ⌊ n / max ( L , n 1 / k 5 ) ⌋ } J \leftarrow\max\{1,\lfloor n/\max(L,n^{1/k^5})\rfloor\} J ← max { 1 , ⌊ n / max ( L , n 1/ k 5 )⌋}
ν ← ( 2 n ⋅ L M − 1 ) / J \nu\leftarrow(2n \cdot L^{M-1})/J ν ← ( 2 n ⋅ L M − 1 ) / J
Initiate an instance of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) , where the clique block S \mathcal{S} S represents the set of all M M M -cliques whose vertices all belong to the same bin
for each arrival of vertex v v v do
j ← j \leftarrow j ← minimum j j j such that ∣ B j ∣ < L |B_j| < L ∣ B j ∣ < L and G [ B j ∪ { v } ] G[B_j \cup\{v\}] G [ B j ∪ { v }] is ( M + 1 ) (M+1) ( M + 1 ) -clique-free
if B j = ∅ B_j = \emptyset B j = ∅ and ∣ { ℓ : 1 ≤ ∣ B ℓ ∣ < L } ∣ = J |\{\ell: 1 \le|B_\ell| < L\}| = J ∣ { ℓ : 1 ≤ ∣ B ℓ ∣ < L } ∣ = J then
Color v v v using the instance of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν )
if the instance of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) terminated by outputting ( S ′ , V ′ ) (\mathcal{S}',V') ( S ′ , V ′ ) then
return vert ( S ′ ) ∪ V ′ \operatorname{vert}(\mathcal{S}') \cup V' vert ( S ′ ) ∪ V ′
else
B j ← B j ∪ { v } B_j \leftarrow B_j \cup\{v\} B j ← B j ∪ { v }
Color v v v with an instance of CliqueFree ( M + 1 ) \operatorname{CliqueFree}(M+1) CliqueFree ( M + 1 ) created for B j B_j B j
and G [ B j ∪ { v } ] G[B_j \cup\{v\}] G [ B j ∪ { v }] is ( M + 1 ) (M+1) ( M + 1 ) -clique-free (line 6). Then, we put v v v into bin B j B_j B j , except when B j B_j B j is empty and there are exactly J J J “incomplete” bins (i.e., bins of sizes between 1 and L − 1 L-1 L − 1 ).
In this exceptional case, we color v v v using CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) instead (lines 7–8). Importantly, v v v meets the input condition of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) defined in Definition 6.9 . This is because:
Since v v v is completely adjacent to at least one clique in each incomplete bin, v v v is completely adjacent to at least J J J cliques in S \mathcal{S} S (i.e., ∣ C ( v ) ∣ ≥ J |\mathcal{C}(v)| \ge J ∣ C ( v ) ∣ ≥ J ).
For each vertex v v v , the number of M M M -cliques that contain v v v and whose vertices all belong to the same bin is at most L M − 1 L^{M-1} L M − 1 , so we have ∣ S ∣ ≤ n ⋅ L M − 1 |\mathcal{S}| \le n \cdot L^{M-1} ∣ S ∣ ≤ n ⋅ L M − 1 .
Finally, once CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) terminates by outputting ( S ′ , V ′ ) (\mathcal{S}',V') ( S ′ , V ′ ) , we output the certificate vert ( S ′ ) ∪ V ′ \operatorname{vert}(\mathcal{S}') \cup V' vert ( S ′ ) ∪ V ′ (lines 9–10). The validity of the output is proven as follows (Lemma 6.11 ), and its size is bounded in the discussion in Subsection 6.10.
Lemma 6.11. The outputted vert ( S ′ ) ∪ V ′ \operatorname{vert}(\mathcal{S}') \cup V' vert ( S ′ ) ∪ V ′ is not k k k -colorable, assuming the output of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) is valid.
Proof. Since the output of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) is valid, there is no k k k -coloring φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] \varphi: (\operatorname{vert}(\mathcal{S}') \cup V') \to[k] φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] such that vert ( S ′ ) \operatorname{vert}(\mathcal{S}') vert ( S ′ ) has at most k k k colors. This directly implies that vert ( S ′ ) ∪ V ′ \operatorname{vert}(\mathcal{S}') \cup V' vert ( S ′ ) ∪ V ′ is not k k k -colorable. □ \square □
Algorithm for CB ( k , M , ν ) \operatorname{CB}(k,M,\nu) CB ( k , M , ν )
We describe an algorithm for the base case CB ( k , M , ν ) \operatorname{CB}(k,M,\nu) CB ( k , M , ν ) .
Algorithm. Our algorithm simply colors all incoming vertices using LOC ( k − M ) \operatorname{LOC}(k-M) LOC ( k − M ) . Let adj ( v ) ∈ C ( v ) \operatorname{adj}(v) \in\mathcal{C}(v) adj ( v ) ∈ C ( v ) be an arbitrarily chosen clique in C ( v ) \mathcal{C}(v) C ( v ) . If LOC ( k − M ) \operatorname{LOC}(k-M) LOC ( k − M ) returns a certificate set X X X and terminates, then we return a pair ( { adj ( v ) : v ∈ X } , X ) (\{\operatorname{adj}(v) : v \in X\}, X) ({ adj ( v ) : v ∈ X } , X ) . The validity of the output is shown as follows (Lemma 6.12 ), and its size is bounded in Subsection 6.10.
Lemma 6.12. Let ( S ′ , V ′ ) : = ( { adj ( v ) : v ∈ X } , X ) (\mathcal{S}',V') := (\{\operatorname{adj}(v) : v \in X\},X) ( S ′ , V ′ ) := ({ adj ( v ) : v ∈ X } , X ) be the outputted pair of the algorithm above, and assume that the output of LOC ( k − M ) \operatorname{LOC}(k-M) LOC ( k − M ) is valid. Then, there is no k k k -coloring of G [ vert ( S ′ ) ∪ V ′ ] G[\operatorname{vert}(\mathcal{S}') \cup V'] G [ vert ( S ′ ) ∪ V ′ ] , φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] \varphi: (\operatorname{vert}(\mathcal{S}') \cup V') \to[k] φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] , such that ∣ { φ ( v ) : v ∈ vert ( S ′ ) } ∣ ≤ M |\{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\}| \le M ∣ { φ ( v ) : v ∈ vert ( S ′ )} ∣ ≤ M .
Proof. Suppose there exists a k k k -coloring φ \varphi φ with ∣ { φ ( v ) : v ∈ vert ( S ′ ) } ∣ ≤ M |\{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\}| \le M ∣ { φ ( v ) : v ∈ vert ( S ′ )} ∣ ≤ M . Without loss of generality, we can assume that { φ ( v ) : v ∈ vert ( S ′ ) } = { 1 , … , M } \{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\} = \{1,\ldots,M\} { φ ( v ) : v ∈ vert ( S ′ )} = { 1 , … , M } . Then, { φ ( v ) : v ∈ S } = { 1 , … , M } \{\varphi(v) : v \in S\} = \{1,\ldots,M\} { φ ( v ) : v ∈ S } = { 1 , … , M } holds for each clique S ∈ S ′ S \in\mathcal{S}' S ∈ S ′ . For each v ∈ V ′ v \in V' v ∈ V ′ , v v v is completely adjacent to adj ( v ) ∈ S ′ \operatorname{adj}(v) \in\mathcal{S}' adj ( v ) ∈ S ′ , and thus φ ( v ) \varphi(v) φ ( v ) must be one of M + 1 , … , k M+1,\ldots,k M + 1 , … , k . However, this implies that the certificate V ′ V' V ′ returned by LOC ( k − M ) \operatorname{LOC}(k-M) LOC ( k − M ) is ( k − M ) (k-M) ( k − M ) -colorable, which contradicts the assumption. Therefore, Lemma 6.12 holds. □ \square □
Algorithm for CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) when ℓ > M \ell> M ℓ > M
Next, we describe an algorithm for the inductive case CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) , where ℓ ∈ { M + 1 , … , k } \ell\in\{M+1,\ldots,k\} ℓ ∈ { M + 1 , … , k } .
Intuition. The key idea is that, by using a small set X ⊆ V X \subseteq V X ⊆ V such that χ ( G [ X ] ) > k − ℓ \chi(G[X]) > k-\ell χ ( G [ X ]) > k − ℓ , we can reduce CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) to ∣ X ∣ |X| ∣ X ∣ subproblems of CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) . Indeed, let X = { x 1 , … , x ∣ X ∣ } X = \{x_1,\ldots,x_{|X|}\} X = { x 1 , … , x ∣ X ∣ } , and for each x j x_j x j , we initiate an instance I j I_j I j of CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) with S ( I j ) : = C ( x j ) \mathcal{S}(I_j) := \mathcal{C}(x_j) S ( I j ) := C ( x j ) . If all instances I 1 , … , I ∣ X ∣ I_1,\ldots,I_{|X|} I 1 , … , I ∣ X ∣ have terminated and each I j I_j I j has returned a pair ( S j ′ , V j ′ ) (\mathcal{S}'_j,V'_j) ( S j ′ , V j ′ ) , then the pair
( S 1 ′ ∪ ⋯ ∪ S ∣ X ∣ ′ , V 1 ′ ∪ ⋯ ∪ V ∣ X ∣ ′ ∪ X ) \left(\mathcal{S}'_1 \cup\cdots\cup\mathcal{S}'_{|X|}, V'_1 \cup\cdots\cup V'_{|X|} \cup X\right) ( S 1 ′ ∪ ⋯ ∪ S ∣ X ∣ ′ , V 1 ′ ∪ ⋯ ∪ V ∣ X ∣ ′ ∪ X )
is a valid output for CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) ; see Figure 19 (a). The validity will be proven in Lemma 6.13 . Therefore, by running LOC ( k − ℓ ) \operatorname{LOC}(k-\ell) LOC ( k − ℓ ) to find an appropriate set X X X , we can proceed by induction on ℓ \ell ℓ . Now, we explain how to implement this idea.
Figure 19. (a) A sketch illustrating the main intuition. Let ( S ′ , V ′ ) (\mathcal{S}', V') ( S ′ , V ′ ) be the outputted set. For any k k k -coloring ϕ \phi ϕ , ∣ { ϕ ( c ) : c ∈ vert ( S ′ ) } ∣ > ℓ |\{\phi(c) : c \in\operatorname{vert}(\mathcal{S}')\}| > \ell ∣ { ϕ ( c ) : c ∈ vert ( S ′ )} ∣ > ℓ must hold. (b) The relationships between instances. (c) A sketch of the procedures when a new vertex arrives.
Algorithm. The pseudocode for the following algorithm is given in Algorithm 6. We maintain I 1 LOC , … , I t LOC I^{\operatorname{LOC}}_1,\ldots,I^{\operatorname{LOC}}_t I 1 LOC , … , I t LOC , the instances of LOC ( k − ℓ ) \operatorname{LOC}(k-\ell) LOC ( k − ℓ ) , listed in chronological order. Initially, only I 1 LOC I^{\operatorname{LOC}}_1 I 1 LOC is initiated, that is, t = 1 t=1 t = 1 (line 1).
When I t LOC I^{\operatorname{LOC}}_t I t LOC terminates with a certificate X = { x 1 , … , x ∣ X ∣ } X=\{x_1,\ldots,x_{|X|}\} X = { x 1 , … , x ∣ X ∣ } , we initiate new instances I t , 1 , … , I t , ∣ X ∣ I_{t,1},\ldots,I_{t,|X|} I t , 1 , … , I t , ∣ X ∣ of CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) (corresponding to I 1 , … , I ∣ X ∣ I_1,\ldots,I_{|X|} I 1 , … , I ∣ X ∣ in the “Intuition” paragraph), where S ( I t , j ) \mathcal{S}(I_{t,j}) S ( I t , j ) is fixed to C ( x j ) \mathcal{C}(x_j) C ( x j ) (lines 12–15). We also record the output set as Q t ← X Q_t \leftarrow X Q t ← X . After that, we initiate I t + 1 LOC I^{\operatorname{LOC}}_{t+1} I t + 1 LOC and let t ← t + 1 t \leftarrow t+1 t ← t + 1 (line 16). The relationship between I t LOC I^{\operatorname{LOC}}_t I t LOC and I t , j I_{t,j} I t , j is illustrated in Figure 19 (b). Note that we use pairwise disjoint colors for all of these instances. Now, when a new vertex v v v arrives, we proceed as follows:
If there exists a non-terminated instance I i , j I_{i,j} I i , j such that ∣ S ( I i , j ) ∩ C ( v ) ∣ ≥ ∣ S ( I i , j ) ∣ / ( 2 ν ) |\mathcal{S}(I_{i,j}) \cap\mathcal{C}(v)| \ge|\mathcal{S}(I_{i,j})|/(2\nu) ∣ S ( I i , j ) ∩ C ( v ) ∣ ≥ ∣ S ( I i , j ) ∣/ ( 2 ν ) , i.e., v v v is completely adjacent to at least a 1 / ( 2 ν ) 1/(2\nu) 1/ ( 2 ν ) fraction of the cliques in S ( I i , j ) \mathcal{S}(I_{i,j}) S ( I i , j ) , we color v v v using I i , j I_{i,j} I i , j (line 6). This is a valid input to CB ( k , ℓ − 1 , 2 ν ) \operatorname{CB}(k,\ell-1,2\nu) CB ( k , ℓ − 1 , 2 ν ) (note the parameter 2 ν 2\nu 2 ν ). If all of I i , 1 , … , I i , ∣ Q i ∣ I_{i,1},\ldots,I_{i,|Q_i|} I i , 1 , … , I i , ∣ Q i ∣ are terminated, we return a pair as written in the “Intuition” paragraph and terminate (lines 7–9).
Otherwise, we color v v v with I t LOC I^{\operatorname{LOC}}_t I t LOC . When I t LOC I^{\operatorname{LOC}}_t I t LOC terminates, we initiate new instances I t , 1 , … , I t , ∣ X ∣ I_{t,1},\ldots,I_{t,|X|} I t , 1 , … , I t , ∣ X ∣ , as discussed above (lines 12–16).
A sketch of the procedure when v v v arrives is illustrated in Figure 19 (c). Importantly, this procedure guarantees t ≤ 3 ν t \le3\nu t ≤ 3 ν ; we prove this in Lemma 6.15.
Lemma 6.13 (Validity of Output). Let ( S ′ , V ′ ) (\mathcal{S}', V') ( S ′ , V ′ ) be the outputted pair of C B ( k , ℓ , ν ) CB(k,\ell,\nu) C B ( k , ℓ , ν ) (in line 9), and assume that the outputs of all instances of C B ( k , ℓ − 1 , 2 ν ) CB(k,\ell-1,2\nu) C B ( k , ℓ − 1 , 2 ν ) and L O C ( k − ℓ ) LOC(k-\ell) L O C ( k − ℓ ) are valid. Then, there is no k k k -coloring of G [ vert ( S ′ ) ∪ V ′ ] G[\operatorname{vert}(\mathcal{S}') \cup V'] G [ vert ( S ′ ) ∪ V ′ ] , φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] \varphi: (\operatorname{vert}(\mathcal{S}') \cup V') \to[k] φ : ( vert ( S ′ ) ∪ V ′ ) → [ k ] , such that ∣ { φ ( v ) : v ∈ vert ( S ′ ) } ∣ ≤ ℓ |\{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\}| \le\ell ∣ { φ ( v ) : v ∈ vert ( S ′ )} ∣ ≤ ℓ .
Proof. Suppose that there exists a k k k -coloring φ \varphi φ with ∣ { φ ( v ) : v ∈ vert ( S ′ ) } ∣ ≤ ℓ |\{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\}| \le\ell ∣ { φ ( v ) : v ∈ vert ( S ′ )} ∣ ≤ ℓ . Let C = { φ ( v ) : v ∈ vert ( S ′ ) } C = \{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\} C = { φ ( v ) : v ∈ vert ( S ′ )} , and C i = { φ ( v ) : v ∈ vert ( S ′ ) } C_i = \{\varphi(v) : v \in\operatorname{vert}(\mathcal{S}')\} C i = { φ ( v ) : v ∈ vert ( S ′ )} for each i i i . Since the output for all instances of C B ( k , ℓ − 1 , 2 ν ) CB(k,\ell-1,2\nu) C B ( k , ℓ − 1 , 2 ν ) are valid, ∣ C i ∣ > ℓ − 1 |C_i| > \ell- 1 ∣ C i ∣ > ℓ − 1 holds. By C i ⊆ C C_i \subseteq C C i ⊆ C , ∣ C ∣ ≤ ℓ |C| \le\ell ∣ C ∣ ≤ ℓ , and ∣ C i ∣ > ℓ − 1 |C_i| > \ell- 1 ∣ C i ∣ > ℓ − 1 , we obtain ∣ C i ∣ = ℓ |C_i| = \ell ∣ C i ∣ = ℓ . This means that
C 1 = C 2 = ⋯ = C ∣ X ∣ . C_1 = C_2 = \cdots= C_{|X|}. C 1 = C 2 = ⋯ = C ∣ X ∣ .
Without loss of generality, we may assume C i = { 1 , 2 , … , ℓ } C_i = \{1,2,\ldots,\ell\} C i = { 1 , 2 , … , ℓ } for each i i i . Let Q i = { q i , 1 , … , q i , ∣ Q i ∣ } Q_i = \{q_{i,1},\ldots,q_{i,|Q_i|}\} Q i = { q i , 1 , … , q i , ∣ Q i ∣ } (at line 9 of Algorithm 6). Since q i , j q_{i,j} q i , j is completely adjacent to all cliques in S ( I i , j ) \mathcal{S}(I_{i,j}) S ( I i , j ) , the color φ ( q i , j ) \varphi(q_{i,j}) φ ( q i , j ) must be one of ℓ + 1 , … , k \ell+1,\ldots,k ℓ + 1 , … , k . However, this means that Q i Q_i Q i is ( k − ℓ ) (k-\ell) ( k − ℓ ) -colorable, which contradicts the assumption that Q i Q_i Q i is a valid output of L O C ( k − ℓ ) LOC(k-\ell) L O C ( k − ℓ ) . Therefore, Lemma 6.13 holds.
Number of Rounds in C B ( k , ℓ , ν ) CB(k,\ell,\nu) C B ( k , ℓ , ν )
We show that the event of creating new instances only occurs at most 3 ν 3\nu 3 ν times in C B ( k , ℓ , ν ) CB(k,\ell,\nu) C B ( k , ℓ , ν ) , i.e., t ≤ 3 ν t \le3\nu t ≤ 3 ν in Algorithm 6.
Lemma 6.14 ([23 ] ). Let ν ≥ 1 \nu\ge1 ν ≥ 1 be a real number. Let S S S be a non-empty set, and let A 1 , … , A t ⊆ S A_1,\ldots,A_t \subseteq S A 1 , … , A t ⊆ S be sets such that ∣ A i ∣ ≥ ∣ S ∣ ν |A_i| \ge\frac{|S|}{\nu} ∣ A i ∣ ≥ ν ∣ S ∣ . If ∣ A i ∩ A j ∣ ≤ ∣ A i ∣ 2 ν |A_i \cap A_j| \le\frac{|A_i|}{2\nu} ∣ A i ∩ A j ∣ ≤ 2 ν ∣ A i ∣ for each i < j i < j i < j , then t < 2 ν t < 2\nu t < 2 ν holds.
Proof. Suppose that t ≥ 2 ν t \ge2\nu t ≥ 2 ν , and let s = ⌈ 2 ν ⌉ s = \lceil2\nu\rceil s = ⌈ 2 ν ⌉ . Let B j = A j ∖ ( A 1 ∪ A 2 ∪ ⋯ ∪ A j − 1 ) B_j = A_j \setminus(A_1 \cup A_2 \cup\cdots\cup A_{j-1}) B j = A j ∖ ( A 1 ∪ A 2 ∪ ⋯ ∪ A j − 1 ) . By the assumptions
Algorithm 6 An algorithm for CB($k,\ell,\nu$) when $\ell \in \{M+1,\ldots,k\}$.
1: $I^{\mathrm{LOC}}_1 \gets$ a new instance of LOC($k-\ell$)
2: $Q_1,Q_2,\ldots \gets \emptyset$
3: $t \gets 1$
4: for each arrival of vertex $v$ do
5: if there exists a non-terminated instance $I_{i,j}$ such that $|\mathcal{S}(I_{i,j}) \cap \mathcal{C}(v)| \ge |\mathcal{S}(I_{i,j})|/(2\nu)$ then
6: color $v$ using $I_{i,j}$ (note that “$\mathcal{C}(v)$” in the instance $I_{i,j}$ is set to $\mathcal{S}(I_{i,j}) \cap \mathcal{C}(v)$)
7: if $I_{i,1},\ldots,I_{i,|Q_i|}$ are all terminated then
8: $(\mathcal{S}'_j,V'_j) \gets$ the returned output of $I_{i,j}$ for all $1 \le j \le |Q_i|$
9: return $(\mathcal{S}'_1 \cup \cdots \cup \mathcal{S}'_{|Q_i|},V'_1 \cup \cdots \cup V'_{|Q_i|} \cup Q_i)$
10: else
11: color $v$ using $I^{\mathrm{LOC}}_t$
12: if $I^{\mathrm{LOC}}_t$ terminated by returning $X=\{x_1,\ldots,x_{|X|}\}$ then
13: $Q_t \gets X$
14: for $j$ in $1,2,\ldots,|X|$ do
15: $I_{t,j} \gets$ a new instance of CB($k,\ell-1,2\nu$) with $\mathcal{S}(I_{t,j}) := \mathcal{C}(x_j)$
16: $I^{\mathrm{LOC}}_{t+1} \gets$ a new instance of LOC($k-\ell$) and $t \gets t+1$
∣ A i ∩ A j ∣ ≤ ∣ A i ∣ 2 ν and ∣ A i ∣ ≥ ∣ S ∣ ν , |A_i \cap A_j| \le\frac{|A_i|}{2\nu} \quad\text{and}\quad|A_i| \ge\frac{|S|}{\nu}, ∣ A i ∩ A j ∣ ≤ 2 ν ∣ A i ∣ and ∣ A i ∣ ≥ ν ∣ S ∣ ,
∑ j = 1 s ∣ B j ∣ ≥ ∑ j = 1 s ( ∣ A j ∣ − ∑ i = 1 j − 1 ∣ A i ∩ A j ∣ ) ≥ ∑ j = 1 s ( ∣ A j ∣ − ∑ i = 1 j − 1 1 2 ν ⋅ ∣ A i ∣ ) ≥ ∑ j = 1 s ∣ A j ∣ − ∑ i = 1 s s − i 2 ν ⋅ ∣ A i ∣ ≥ ∑ i = 1 s 2 ν − s + i 2 ν ⋅ ∣ A i ∣ ≥ ∑ i = 1 s 2 ν − s + i 2 ν 2 ⋅ ∣ S ∣ . \begin{aligned}
\sum_{j=1}^{s}|B_j| \ge\sum_{j=1}^{s}\left(|A_j|-\sum_{i=1}^{j-1}|A_i\cap A_j|\right) \\
&\ge\sum_{j=1}^{s}\left(|A_j|-\sum_{i=1}^{j-1}\frac{1}{2\nu}\cdot|A_i|\right) \\
&\ge\sum_{j=1}^{s}|A_j|-\sum_{i=1}^{s}\frac{s-i}{2\nu}\cdot|A_i|
\ge\sum_{i=1}^{s}\frac{2\nu-s+i}{2\nu}\cdot|A_i|
\ge\sum_{i=1}^{s}\frac{2\nu-s+i}{2\nu^2}\cdot|S|.
\end{aligned} j = 1 ∑ s ∣ B j ∣ ≥ j = 1 ∑ s ( ∣ A j ∣ − i = 1 ∑ j − 1 ∣ A i ∩ A j ∣ ) ≥ j = 1 ∑ s ( ∣ A j ∣ − i = 1 ∑ j − 1 2 ν 1 ⋅ ∣ A i ∣ ) ≥ j = 1 ∑ s ∣ A j ∣ − i = 1 ∑ s 2 ν s − i ⋅ ∣ A i ∣ ≥ i = 1 ∑ s 2 ν 2 ν − s + i ⋅ ∣ A i ∣ ≥ i = 1 ∑ s 2 ν 2 2 ν − s + i ⋅ ∣ S ∣.
However, we have ∑ i = 1 s ∣ B i ∣ ≤ ∣ S ∣ \sum_{i=1}^{s}|B_i| \le|S| ∑ i = 1 s ∣ B i ∣ ≤ ∣ S ∣ because B 1 , … , B s B_1,\ldots,B_s B 1 , … , B s are disjoint. This contradicts the inequality above at s = ⌈ 2 ν ⌉ s=\lceil2\nu\rceil s = ⌈ 2 ν ⌉ . Therefore, t < 2 ν t<2\nu t < 2 ν holds. □ \square □
Lemma 6.15. In each run of Algorithm 6 for CB (k , ℓ , ν k,\ell,\nu k , ℓ , ν ), we have t ≤ 3 ν t\le3\nu t ≤ 3 ν .
Proof. For each i ∈ { 1 , … , t − 1 } i\in\{1,\ldots,t-1\} i ∈ { 1 , … , t − 1 } , let p i p_i p i be an index such that I i , p i I_{i,p_i} I i , p i has not yet been terminated (such an index must exist while CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) is not terminated). Then, for each i < j i<j i < j ,
∣ S ( I i , p i ) ∩ S ( I j , p j ) ∣ ≤ ∣ S ( I i , p i ) ∣ 2 ν . |\mathcal{S}(I_{i,p_i})\cap\mathcal{S}(I_{j,p_j})|
\le\frac{|\mathcal{S}(I_{i,p_i})|}{2\nu}. ∣ S ( I i , p i ) ∩ S ( I j , p j ) ∣ ≤ 2 ν ∣ S ( I i , p i ) ∣ .
This is because, otherwise, the vertex q j , p j q_{j,p_j} q j , p j must be colored by instance I i , p i I_{i,p_i} I i , p i (in lines 5–6 of Algorithm 6) and thus I j , p j I_{j,p_j} I j , p j would not be created, a contradiction. In addition, ∣ S ( I i , p i ) ∣ ≥ ∣ S ∣ / ν |\mathcal{S}(I_{i,p_i})|\ge|\mathcal{S}|/\nu ∣ S ( I i , p i ) ∣ ≥ ∣ S ∣/ ν holds by the input assumption of CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ). By Lemma 6.14 (with A i : = S ( I i , p i ) A_i:=\mathcal{S}(I_{i,p_i}) A i := S ( I i , p i ) and S : = S S:=\mathcal{S} S := S ), t < 2 ν + 1 ≤ 3 ν t<2\nu+1\le3\nu t < 2 ν + 1 ≤ 3 ν holds. □ \square □
Analysis Part I: Certificate Size & Correctness
Now, we start the analysis of the algorithm. First, we analyze the sizes of the returned certificates. We let f k f_k f k be the upper bound on the size ∣ X ∣ |X| ∣ X ∣ of a certificate X X X returned by LOC(k k k ). We also let g k , ℓ g_{k,\ell} g k , ℓ be the upper bound on the size ∣ vert ( S ′ ) ∪ V ′ ∣ |\operatorname{vert}(\mathcal{S}') \cup V'| ∣ vert ( S ′ ) ∪ V ′ ∣ of a certificate ( S ′ , V ′ ) (\mathcal{S}', V') ( S ′ , V ′ ) returned by CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ). Note that these bounds can also be used in the definition of each subproblem; see Definition 6.8 and Definition 6.9 . Then, the following inequalities hold:
Lemma 6.16. For k ≤ M k \le M k ≤ M , we have f k ≤ M + 1 f_k \le M+1 f k ≤ M + 1 .
Proof. By Subsection 6.6, LOC(k k k ) returns an ( M + 1 ) (M+1) ( M + 1 ) -clique, so Lemma 6.16 holds. □ \square □
Lemma 6.17. For k > M k > M k > M , we have f k ≤ g k , k f_k \le g_{k,k} f k ≤ g k , k .
Proof. By Subsection 6.6, LOC(k k k ) returns vert ( S ′ ) ∪ V ′ \operatorname{vert}(\mathcal{S}') \cup V' vert ( S ′ ) ∪ V ′ when CB(k , k , ν k,k,\nu k , k , ν ) terminates by returning a pair ( S ′ , V ′ ) (\mathcal{S}',V') ( S ′ , V ′ ) . Therefore, f k ≤ g k , k f_k \le g_{k,k} f k ≤ g k , k . □ \square □
Lemma 6.18. For k ≥ M k \ge M k ≥ M , we have g k , M ≤ ( M + 1 ) ⋅ f k − M g_{k,M} \le(M+1) \cdot f_{k-M} g k , M ≤ ( M + 1 ) ⋅ f k − M .
Proof. We denote the returned pair in CB(k , M , ν k,M,\nu k , M , ν ) as ( S ′ , V ′ ) (\mathcal{S}',V') ( S ′ , V ′ ) . By Subsection 6.7, CB(k , M , ν k,M,\nu k , M , ν ) returns a pair ( { adj ( v ) : v ∈ X } , X ) (\{\operatorname{adj}(v):v\in X\},X) ({ adj ( v ) : v ∈ X } , X ) when an instance of LOC(k − M k-M k − M ) terminates by returning a set X X X . Since adj ( v ) \operatorname{adj}(v) adj ( v ) is an M M M -clique (see Subsection 6.7), ∣ vert ( S ′ ) ∣ ≤ M ∣ X ∣ |\operatorname{vert}(\mathcal{S}')| \le M|X| ∣ vert ( S ′ ) ∣ ≤ M ∣ X ∣ , and therefore ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ ( M + 1 ) ∣ X ∣ ≤ ( M + 1 ) f k − M |\operatorname{vert}(\mathcal{S}')\cup V'| \le(M+1)|X| \le(M+1)f_{k-M} ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ ( M + 1 ) ∣ X ∣ ≤ ( M + 1 ) f k − M , proving Lemma 6.18 . □ \square □
Lemma 6.19. For k > M k > M k > M and ℓ ∈ { M + 1 , … , k } \ell\in\{M+1,\ldots,k\} ℓ ∈ { M + 1 , … , k } , we have g k , ℓ ≤ f k − ℓ ⋅ ( g k , ℓ − 1 + 1 ) g_{k,\ell} \le f_{k-\ell}\cdot(g_{k,\ell-1}+1) g k , ℓ ≤ f k − ℓ ⋅ ( g k , ℓ − 1 + 1 ) .
Proof. We denote the pair returned in CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) as ( S ′ , V ′ ) (\mathcal{S}',V') ( S ′ , V ′ ) . By Subsection 6.8, as shown in lines 8–9 of Algorithm 6, CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) returns
( S ′ , V ′ ) : = ( S 1 ′ ∪ ⋯ ∪ S ∣ Q i ∣ ′ , V 1 ′ ∪ ⋯ ∪ V ∣ Q i ∣ ′ ∪ Q i ) (\mathcal{S}',V') := \left(\mathcal{S}'_1\cup\cdots\cup\mathcal{S}'_{|Q_i|},V'_1\cup\cdots\cup V'_{|Q_i|}\cup Q_i\right) ( S ′ , V ′ ) := ( S 1 ′ ∪ ⋯ ∪ S ∣ Q i ∣ ′ , V 1 ′ ∪ ⋯ ∪ V ∣ Q i ∣ ′ ∪ Q i )
if the instances I i , 1 , … , I i , ∣ Q i ∣ I_{i,1},\ldots,I_{i,|Q_i|} I i , 1 , … , I i , ∣ Q i ∣ returned ( S 1 ′ , V 1 ′ ) , … , ( S ∣ Q i ∣ ′ , V ∣ Q i ∣ ′ ) (\mathcal{S}'_1,V'_1),\ldots,(\mathcal{S}'_{|Q_i|},V'_{|Q_i|}) ( S 1 ′ , V 1 ′ ) , … , ( S ∣ Q i ∣ ′ , V ∣ Q i ∣ ′ ) , respectively. Since ∣ vert ( S i ′ ) ∪ V i ′ ∣ ≤ g k , ℓ − 1 |\operatorname{vert}(\mathcal{S}'_i)\cup V'_i|\le g_{k,\ell-1} ∣ vert ( S i ′ ) ∪ V i ′ ∣ ≤ g k , ℓ − 1 and ∣ Q i ∣ ≤ f k − ℓ |Q_i|\le f_{k-\ell} ∣ Q i ∣ ≤ f k − ℓ , ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ f k − ℓ ⋅ ( g k , ℓ − 1 + 1 ) |\operatorname{vert}(\mathcal{S}')\cup V'|\le f_{k-\ell}\cdot(g_{k,\ell-1}+1) ∣ vert ( S ′ ) ∪ V ′ ∣ ≤ f k − ℓ ⋅ ( g k , ℓ − 1 + 1 ) holds, proving Lemma 6.19 . □ \square □
Lemma 6.20 (Correctness). When we set f k f_k f k and g k , ℓ g_{k,\ell} g k , ℓ according to Lemma 6.16 –Lemma 6.19 , the outputs of the algorithm for LOC(k k k ) and CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) are valid.
Proof. We show by induction on both k k k and ℓ \ell ℓ . For LOC(k k k ) (see Definition 6.8 for the definition), the output is valid for k ≤ M k\le M k ≤ M because the output is an ( M + 1 ) (M+1) ( M + 1 ) -clique and by Lemma 6.16 , and the output is also valid for k > M k>M k > M by Lemma 6.11 and Lemma 6.17 . For CB(k , ℓ , ν k,\ell,\nu k , ℓ , ν ) (see Definition 6.9 for the definition), the output is valid for ℓ = M \ell=M ℓ = M by Lemma 6.12 and Lemma 6.18 , and the output is also valid for ℓ > M \ell>M ℓ > M by Lemma 6.13 and Lemma 6.19 . Therefore, Lemma 6.20 holds. □ \square □
Furthermore, we analyze the growth of f k f_k f k in the following two lemmas.
Lemma 6.21. For k > M k>M k > M , we have f k + 1 ≤ ( M + 1 ) × ( f 0 + 1 ) × ⋯ × ( f k − M + 1 ) f_k+1\le(M+1)\times(f_0+1)\times\cdots\times(f_{k-M}+1) f k + 1 ≤ ( M + 1 ) × ( f 0 + 1 ) × ⋯ × ( f k − M + 1 )
Proof. First, we prove by induction on ℓ \ell ℓ that g k , ℓ + 1 ≤ ( M + 1 ) × ( f k − ℓ + 1 ) × ⋯ × ( f k − M + 1 ) g_{k,\ell}+1\leq(M+1)\times(f_{k-\ell}+1)\times\cdots\times(f_{k-M}+1) g k , ℓ + 1 ≤ ( M + 1 ) × ( f k − ℓ + 1 ) × ⋯ × ( f k − M + 1 ) holds for all ℓ ≥ M \ell\geq M ℓ ≥ M . When ℓ = M \ell=M ℓ = M , the inequality holds due to Lemma 6.18 . Assume that the inequality holds at ℓ = ℓ ′ − 1 \ell=\ell'-1 ℓ = ℓ ′ − 1 . Then, this also holds at ℓ = ℓ ′ \ell=\ell' ℓ = ℓ ′ as follows:
g k , ℓ ′ + 1 ≤ f k − ℓ ′ ⋅ ( g k , ℓ ′ − 1 + 1 ) + 1 ≤ f k − ℓ ′ ⋅ ( ( M + 1 ) × ( f k − ℓ ′ + 1 + 1 ) × ⋯ × ( f k − M + 1 ) ) + 1 ≤ ( M + 1 ) × ( f k − ℓ ′ + 1 ) × ⋯ × ( f k − M + 1 ) \begin{aligned}
g_{k,\ell'}+1 &\leq f_{k-\ell'}\cdot(g_{k,\ell'-1}+1)+1\\
&\leq f_{k-\ell'}\cdot((M+1)\times(f_{k-\ell'+1}+1)\times\cdots\times(f_{k-M}+1))+1\\
&\leq(M+1)\times(f_{k-\ell'}+1)\times\cdots\times(f_{k-M}+1)
\end{aligned} g k , ℓ ′ + 1 ≤ f k − ℓ ′ ⋅ ( g k , ℓ ′ − 1 + 1 ) + 1 ≤ f k − ℓ ′ ⋅ (( M + 1 ) × ( f k − ℓ ′ + 1 + 1 ) × ⋯ × ( f k − M + 1 )) + 1 ≤ ( M + 1 ) × ( f k − ℓ ′ + 1 ) × ⋯ × ( f k − M + 1 )
where the first inequality follows from Lemma 6.19 and the second inequality is given by induction on ℓ \ell ℓ . Therefore, g k , k + 1 ≤ ( M + 1 ) × ( f 0 + 1 ) × ⋯ × ( f k − M + 1 ) g_{k,k+1}\leq(M+1)\times(f_0+1)\times\cdots\times(f_{k-M}+1) g k , k + 1 ≤ ( M + 1 ) × ( f 0 + 1 ) × ⋯ × ( f k − M + 1 ) . By Lemma 6.17 , Lemma 6.21 holds.
Lemma 6.22. Assuming N N N is large enough, f k ≤ L f_k\leq L f k ≤ L holds for all k ≤ M 2 k\leq M^2 k ≤ M 2 .
Proof. Let F k = log M + 1 ( f k + 1 ) F_k=\log_{M+1}(f_k+1) F k = log M + 1 ( f k + 1 ) . Then, by Lemma 6.21 , F k ≤ M F_k\leq M F k ≤ M for k ≤ M k\leq M k ≤ M and F k ≤ F 0 + ⋯ + F k − M + 1 F_k\leq F_0+\cdots+F_{k-M+1} F k ≤ F 0 + ⋯ + F k − M + 1 for k > M k>M k > M . Thus, we have F k ≤ M 2 ⌈ k / M ⌉ + 1 F_k\leq M^{2\lceil k/M\rceil+1} F k ≤ M 2 ⌈ k / M ⌉ + 1 for k ≤ M 2 k\leq M^2 k ≤ M 2 , since this obviously holds for k ≤ M k\leq M k ≤ M and
F k ≤ 1 + ∑ i = 0 k − M F i ≤ 1 + ∑ i = 0 k − M M 2 ⌈ i / M ⌉ − 1 ≤ M 2 ⋅ M 2 ⌈ k / M ⌉ − 1 = M 2 ⌈ k / M ⌉ + 1 F_k\leq1+\sum_{i=0}^{k-M}F_i\leq1+\sum_{i=0}^{k-M}M^{2\lceil i/M\rceil-1}\leq M^2\cdot M^{2\lceil k/M\rceil-1}=M^{2\lceil k/M\rceil+1} F k ≤ 1 + i = 0 ∑ k − M F i ≤ 1 + i = 0 ∑ k − M M 2 ⌈ i / M ⌉ − 1 ≤ M 2 ⋅ M 2 ⌈ k / M ⌉ − 1 = M 2 ⌈ k / M ⌉ + 1
for M < k ≤ M 2 M<k\leq M^2 M < k ≤ M 2 , and F k ≤ M 2 M + 1 F_k\leq M^{2M+1} F k ≤ M 2 M + 1 holds (k ≤ M 2 k\leq M^2 k ≤ M 2 ). By M = ⌊ ( log log N ) 1 − ϵ / 2 ⌋ M=\lfloor(\log\log N)^{1-\epsilon/2}\rfloor M = ⌊( log log N ) 1 − ϵ /2 ⌋ and L = ⌊ N 1 / M 11 ⌋ L=\lfloor N^{1/M^{11}}\rfloor L = ⌊ N 1/ M 11 ⌋ ,
log log ( f k + 1 ) = log ( F k log ( M + 1 ) ) ≤ log ( M 2 M + 1 log ( M + 1 ) ) ≤ log ( M 3 M log ( M + 1 ) ) = 3 M log M + log log ( M + 1 ) = 3 ( log log N ) 1 − ϵ / 2 ⋅ log ( log log N ) 1 − ϵ / 2 + o ( log log N ) = o ( log log N ) , log log L ≥ ( log log N 1 / M 11 ) / 2 = log ( ( log N ) / M 11 ) / 2 = log ( ( log N ) / ( log log N ) 11 − 5.5 ϵ ) / 2 = ( log log N − log ( log log N ) 11 − 5.5 ϵ ) / 2 = Θ ( log log N ) . \begin{aligned}
\log\log(f_k+1)&=\log(F_k\log(M+1))\leq\log(M^{2M+1}\log(M+1))\\
&\leq\log(M^{3M}\log(M+1))=3M\log M+\log\log(M+1)\\
&=3(\log\log N)^{1-\epsilon/2}\cdot\log(\log\log N)^{1-\epsilon/2}+o(\log\log N)=o(\log\log N),\\
\log\log L&\geq(\log\log N^{1/M^{11}})/2=\log((\log N)/M^{11})/2\\
&=\log((\log N)/(\log\log N)^{11-5.5\epsilon})/2\\
&=(\log\log N-\log(\log\log N)^{11-5.5\epsilon})/2=\Theta(\log\log N).
\end{aligned} log log ( f k + 1 ) log log L = log ( F k log ( M + 1 )) ≤ log ( M 2 M + 1 log ( M + 1 )) ≤ log ( M 3 M log ( M + 1 )) = 3 M log M + log log ( M + 1 ) = 3 ( log log N ) 1 − ϵ /2 ⋅ log ( log log N ) 1 − ϵ /2 + o ( log log N ) = o ( log log N ) , ≥ ( log log N 1/ M 11 ) /2 = log (( log N ) / M 11 ) /2 = log (( log N ) / ( log log N ) 11 − 5.5 ϵ ) /2 = ( log log N − log ( log log N ) 11 − 5.5 ϵ ) /2 = Θ ( log log N ) .
Therefore, f k + 1 ≤ L f_k+1\leq L f k + 1 ≤ L for k ≤ M 2 k\leq M^2 k ≤ M 2 , and Lemma 6.22 follows.
Analysis Part II: Number of Colors Used
Finally, we analyze the number of colors used in the algorithm to solve LOC ( M 2 ) \operatorname{LOC}(M^2) LOC ( M 2 ) on N N N vertices; we eventually prove that we use at most 3 N / M 3N/M 3 N / M colors. In the following proof, we may omit parameters by using notation such as LOC ( ⋅ ) \operatorname{LOC}(\cdot) LOC ( ⋅ ) , which refers to LOC ( k ) \operatorname{LOC}(k) LOC ( k ) for any k k k .
Lemma 6.23. Assuming N N N is sufficiently large, each call to CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) satisfies ν ≤ N 3 / M 5 \nu\leq N^{3/M^5} ν ≤ N 3/ M 5 .
Proof. Consider a call to CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) . The algorithm for LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) (for the same k k k ) initiates an instance of CB ( k , k , ν ) \operatorname{CB}(k,k,\nu) CB ( k , k , ν ) where
ν = 2 n ⋅ L M − 1 J ≤ ( 2 n ⋅ L M − 1 ) ⋅ 2 max ( L , n 1 / k 5 ) n ≤ 4 ⋅ L M − 1 ⋅ max ( L , n 1 / k 5 ) ≤ 4 ⋅ N 1 / M 10 ⋅ max ( N 1 / M 11 , N 1 / M 5 ) ≤ 4 N 1 / M 10 + 1 / M 5 ≤ N 2 / M 5 . \begin{aligned}
\nu&=\frac{2n\cdot L^{M-1}}{J}\leq(2n\cdot L^{M-1})\cdot\frac{2\max(L,n^{1/k^5})}{n}\\
&\leq4\cdot L^{M-1}\cdot\max(L,n^{1/k^5})\\
&\leq4\cdot N^{1/M^{10}}\cdot\max(N^{1/M^{11}},N^{1/M^5})\leq4N^{1/M^{10}+1/M^5}\leq N^{2/M^5}.
\end{aligned} ν = J 2 n ⋅ L M − 1 ≤ ( 2 n ⋅ L M − 1 ) ⋅ n 2 max ( L , n 1/ k 5 ) ≤ 4 ⋅ L M − 1 ⋅ max ( L , n 1/ k 5 ) ≤ 4 ⋅ N 1/ M 10 ⋅ max ( N 1/ M 11 , N 1/ M 5 ) ≤ 4 N 1/ M 10 + 1/ M 5 ≤ N 2/ M 5 .
This follows from the definitions of J J J and ν \nu ν (in Subsection 6.6) and the facts that L = N 1 / M 11 L=N^{1/M^{11}} L = N 1/ M 11 and k > M k>M k > M . Denote this value of ν \nu ν by ν 0 \nu_0 ν 0 . Then, for ℓ = k − 1 , … , M \ell=k-1,\ldots,M ℓ = k − 1 , … , M , the algorithm recursively calls CB ( k , ℓ , ν ) \operatorname{CB}(k,\ell,\nu) CB ( k , ℓ , ν ) with ν = 2 k − ℓ ν 0 \nu=2^{k-\ell}\nu_0 ν = 2 k − ℓ ν 0 . Since k ≤ M 2 k\le M^2 k ≤ M 2 , we have ν ≤ 2 M 2 ⋅ N 2 / M 5 ≤ N 3 / M 5 \nu\le2^{M^2}\cdot N^{2/M^5}\le N^{3/M^5} ν ≤ 2 M 2 ⋅ N 2/ M 5 ≤ N 3/ M 5 . Therefore, Lemma 6.23 holds.
Lemma 6.24. Assume that N N N is sufficiently large. Let k ∈ { M + 1 , … , M 2 } k\in\{M+1,\ldots,M^2\} k ∈ { M + 1 , … , M 2 } . The algorithm for LOC ( k ) \operatorname{LOC}(k) LOC ( k ) invokes at most N 4 / M 3 N^{4/M^3} N 4/ M 3 instances of CB ( k , ℓ , ⋅ ) \operatorname{CB}(k,\ell,\cdot) CB ( k , ℓ , ⋅ ) for each ℓ ∈ { M , … , k } \ell\in\{M,\ldots,k\} ℓ ∈ { M , … , k } , including indirectly invoked instances.
Proof. Let h ℓ h_\ell h ℓ be the number of CB ( k , ℓ , ⋅ ) \operatorname{CB}(k,\ell,\cdot) CB ( k , ℓ , ⋅ ) instances initiated during the run of LOC ( k ) \operatorname{LOC}(k) LOC ( k ) . By Definition 6.9 and Lemma 6.15, one CB ( k , ℓ , ⋅ ) \operatorname{CB}(k,\ell,\cdot) CB ( k , ℓ , ⋅ ) instance initiates at most 3 ν ⋅ f k − ℓ 3\nu\cdot f_{k-\ell} 3 ν ⋅ f k − ℓ instances of CB ( k , ℓ − 1 , ⋅ ) \operatorname{CB}(k,\ell-1,\cdot) CB ( k , ℓ − 1 , ⋅ ) . Thus, h ℓ − 1 ≤ ( h ℓ × 3 ν ) × f k − ℓ h_{\ell-1}\le(h_\ell\times3\nu)\times f_{k-\ell} h ℓ − 1 ≤ ( h ℓ × 3 ν ) × f k − ℓ . In addition, since LOC ( k ) \operatorname{LOC}(k) LOC ( k ) invokes LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) at most log 2 N + 1 \log_2N+1 log 2 N + 1 times, we have h k ≤ log 2 N + 1 h_k\le\log_2N+1 h k ≤ log 2 N + 1 . Therefore, for ℓ ≥ M \ell\ge M ℓ ≥ M ,
h ℓ ≤ ( 3 ν ) k − ℓ × ( f 0 × ⋯ × f k − ℓ − 1 ) × ( log 2 N + 1 ) ≤ ( 3 ν ) M 2 × L k − ℓ × N 1 / M 11 ≤ ( 3 N 3 / M 5 ) M 2 × N 1 / M 9 × N 1 / M 11 ≤ N 4 / M 3 . \begin{aligned}
h_\ell&\le(3\nu)^{k-\ell}\times(f_0\times\cdots\times f_{k-\ell-1})\times(\log_2N+1)\\
&\le(3\nu)^{M^2}\times L^{k-\ell}\times N^{1/M^{11}}\\
&\le(3N^{3/M^5})^{M^2}\times N^{1/M^9}\times N^{1/M^{11}}\le N^{4/M^3}.
\end{aligned} h ℓ ≤ ( 3 ν ) k − ℓ × ( f 0 × ⋯ × f k − ℓ − 1 ) × ( log 2 N + 1 ) ≤ ( 3 ν ) M 2 × L k − ℓ × N 1/ M 11 ≤ ( 3 N 3/ M 5 ) M 2 × N 1/ M 9 × N 1/ M 11 ≤ N 4/ M 3 .
The first inequality is due to h ℓ − 1 ≤ ( h ℓ × 3 ν ) × f k − ℓ h_{\ell-1}\le(h_\ell\times3\nu)\times f_{k-\ell} h ℓ − 1 ≤ ( h ℓ × 3 ν ) × f k − ℓ , the second inequality is due to k ≤ M 2 k\le M^2 k ≤ M 2 and Lemma 6.22, and the third inequality is due to Lemma 6.23, L = N 1 / M 11 L=N^{1/M^{11}} L = N 1/ M 11 , and k − ℓ ≤ M 2 k-\ell\le M^2 k − ℓ ≤ M 2 . This completes the proof.
Lemma 6.25. Assume that N N N is sufficiently large. An instance of LOC ( M 2 ) \operatorname{LOC}(M^2) LOC ( M 2 ) invokes a total of at most N 5 / M N^{5/M} N 5/ M instances of LOC ( ⋅ ) \operatorname{LOC}(\cdot) LOC ( ⋅ ) , including indirectly invoked instances.
Proof. Let r k r_k r k be the number of LOC ( ⋅ ) \operatorname{LOC}(\cdot) LOC ( ⋅ ) instances invoked by LOC ( k ) \operatorname{LOC}(k) LOC ( k ) , including LOC ( k ) \operatorname{LOC}(k) LOC ( k ) itself. For k ≤ M k\le M k ≤ M , obviously r k = 1 r_k=1 r k = 1 holds. For k > M k>M k > M , due to Lemma 6.24 , LOC ( k ) \operatorname{LOC}(k) LOC ( k ) initiates at most N 4 / M 3 N^{4/M^3} N 4/ M 3 instances of CB ( k , ℓ , ⋅ ) \operatorname{CB}(k,\ell,\cdot) CB ( k , ℓ , ⋅ ) for each M ≤ ℓ ≤ k M\le\ell\le k M ≤ ℓ ≤ k . By Lemma 6.15, each CB ( k , ℓ , ⋅ ) \operatorname{CB}(k,\ell,\cdot) CB ( k , ℓ , ⋅ ) invokes at most 3 ν 3\nu 3 ν instances of LOC ( k − ℓ ) \operatorname{LOC}(k-\ell) LOC ( k − ℓ ) . Therefore,
r k ≤ ( 3 ν ⋅ N 4 / M 3 ) ⋅ ( r 0 + ⋯ + r k − M ) + 1 ≤ 3 N 4 / M 3 + 3 / M 5 ⋅ ( r 0 + ⋯ + r k − M ) + 1 ≤ N 5 / M 3 ⋅ ( r 0 + ⋯ + r k − M ) \begin{aligned}
r_k &\le(3\nu\cdot N^{4/M^3})\cdot(r_0+\cdots+r_{k-M})+1\\
&\le3N^{4/M^3+3/M^5}\cdot(r_0+\cdots+r_{k-M})+1\\
&\le N^{5/M^3}\cdot(r_0+\cdots+r_{k-M})
\end{aligned} r k ≤ ( 3 ν ⋅ N 4/ M 3 ) ⋅ ( r 0 + ⋯ + r k − M ) + 1 ≤ 3 N 4/ M 3 + 3/ M 5 ⋅ ( r 0 + ⋯ + r k − M ) + 1 ≤ N 5/ M 3 ⋅ ( r 0 + ⋯ + r k − M )
and the inequality above holds with r k = N 5 k / M 3 r_k=N^{5k/M^3} r k = N 5 k / M 3 (k > M k>M k > M ). Therefore, LOC ( M 2 ) \operatorname{LOC}(M^2) LOC ( M 2 ) invokes at most N 5 / M N^{5/M} N 5/ M instances of LOC ( ⋅ ) \operatorname{LOC}(\cdot) LOC ( ⋅ ) .
Lemma 6.26. Consider an instance LOC ( k ) \operatorname{LOC}(k) LOC ( k ) (k ≤ M 2 k\le M^2 k ≤ M 2 ) received n n n vertices and b b b of them are (directly) put into bins (note that n n n and b b b are unknown). Assuming N N N is large enough, at most b L + 4 ⋅ n 1 − 1 / M 10 \frac{b}{L}+4\cdot n^{1-1/M^{10}} L b + 4 ⋅ n 1 − 1/ M 10 bins are created.
Proof. Consider the case k > M k>M k > M , because the case k ≤ M k\le M k ≤ M is trivial. Suppose that LOC ( k ) \operatorname{LOC}(k) LOC ( k ) initiated instances for LOC ′ ( k ) \operatorname{LOC}'(k) LOC ′ ( k ) on n 0 , n 1 , … , n m − 1 n_0,n_1,\ldots,n_{m-1} n 0 , n 1 , … , n m − 1 vertices where n i = 2 i n_i=2^i n i = 2 i , and the n i n_i n i -vertex instance (directly) put b i b_i b i vertices to bins. Then, since J ≤ ( n i ) 1 − 1 / M 10 J\le(n_i)^{1-1/M^{10}} J ≤ ( n i ) 1 − 1/ M 10 , the n i n_i n i -vertex instance creates at most ( n i ) 1 − 1 / M 10 + b i L (n_i)^{1-1/M^{10}}+\frac{b_i}{L} ( n i ) 1 − 1/ M 10 + L b i bins. Therefore, at most
∑ i = 0 m − 1 ( n i ) 1 − 1 / M 10 + b i L ≤ ∑ i = 0 ⌊ log 2 n ⌋ ( 2 i ) 1 − 1 / M 10 + b L ≤ 4 ⋅ n 1 − 1 / M 10 + b L \sum_{i=0}^{m-1}(n_i)^{1-1/M^{10}}+\frac{b_i}{L}
\le\sum_{i=0}^{\lfloor\log_2 n\rfloor}(2^i)^{1-1/M^{10}}+\frac{b}{L}
\le4\cdot n^{1-1/M^{10}}+\frac{b}{L} i = 0 ∑ m − 1 ( n i ) 1 − 1/ M 10 + L b i ≤ i = 0 ∑ ⌊ l o g 2 n ⌋ ( 2 i ) 1 − 1/ M 10 + L b ≤ 4 ⋅ n 1 − 1/ M 10 + L b
bins are created in LOC(k k k ), which proves the lemma. □
Theorem 6.27. Assuming N N N is sufficiently large, LOC(M 2 M^2 M 2 ) uses at most 3 N M \frac{3N}{M} M 3 N colors.
Proof. Assume that LOC(M 2 M^2 M 2 ) invokes m m m instances of LOC(⋅ \cdot ⋅ ), the i i i -th instance receives n i n_i n i vertices, and b i b_i b i of them are put into bins. First, by Lemma 6.25 , LOC(M 2 M^2 M 2 ) invokes at most N 5 / M N^{5/M} N 5/ M instances of LOC(⋅ \cdot ⋅ ), and therefore m ≤ N 5 / M m \le N^{5/M} m ≤ N 5/ M . Second, ∑ i b i ≤ N \sum_i b_i \le N ∑ i b i ≤ N holds because each vertex v v v that arrives during the run of LOC(k k k ) is eventually placed in one of the bins for some LOC(⋅ \cdot ⋅ ) instance. Third, ∑ i n i ≤ N M \sum_i n_i \le NM ∑ i n i ≤ N M holds, because for each arrival of vertex v v v , at most M M M calls to LOC(⋅ \cdot ⋅ ) instances happen (the worst case is LOC(M 2 M^2 M 2 ) → \to → LOC(M 2 − M M^2-M M 2 − M ) → ⋯ → \to\cdots\to → ⋯ → LOC(M M M )).
Therefore, by Lemma 6.26 , we can bound the total number of bins created as follows. For readability, we highlight the terms in different colors.
∑ i = 1 m ( 4 ⋅ n i 1 − 1 / M 10 + b i L ) ≤ 4 ⋅ m ⋅ ( ∑ i n i m ) 1 − 1 / M 10 + ∑ i b i L \sum_{i=1}^{m}\left(4\cdot n_i^{1-1/M^{10}}+\frac{b_i}{L}\right)
\le4\cdot m\cdot\left(\frac{\sum_i n_i}{m}\right)^{1-1/M^{10}}+\frac{\sum_i b_i}{L} i = 1 ∑ m ( 4 ⋅ n i 1 − 1/ M 10 + L b i ) ≤ 4 ⋅ m ⋅ ( m ∑ i n i ) 1 − 1/ M 10 + L ∑ i b i ≤ 4 ⋅ N 5 / M ⋅ ( N M N 5 / M ) 1 − 1 / M 10 + N L \le4\cdot N^{5/M}\cdot\left(\frac{NM}{N^{5/M}}\right)^{1-1/M^{10}}+\frac{N}{L} ≤ 4 ⋅ N 5/ M ⋅ ( N 5/ M N M ) 1 − 1/ M 10 + L N ≤ 4 ⋅ N 5 / M ⋅ N ( 1 − 5 / M ) ( 1 − 1 / M 10 ) ⋅ M + N L \le4\cdot N^{5/M}\cdot N^{(1-5/M)(1-1/M^{10})}\cdot M+\frac{N}{L} ≤ 4 ⋅ N 5/ M ⋅ N ( 1 − 5/ M ) ( 1 − 1/ M 10 ) ⋅ M + L N ≤ 4 ⋅ N 5 / M + ( 1 − 5 / M ) ( 1 − 1 / M 10 ) ⋅ N 1 / M 12 + N L \le4\cdot N^{5/M+(1-5/M)(1-1/M^{10})}\cdot N^{1/M^{12}}+\frac{N}{L} ≤ 4 ⋅ N 5/ M + ( 1 − 5/ M ) ( 1 − 1/ M 10 ) ⋅ N 1/ M 12 + L N ≤ 4 ⋅ N 1 − 1 / M 10 + 5 / M 11 + 1 / M 12 + N L ≤ N L + N L = 2 N L . \le4\cdot N^{1-1/M^{10}+5/M^{11}+1/M^{12}}+\frac{N}{L}
\le\frac{N}{L}+\frac{N}{L}=\frac{2N}{L}. ≤ 4 ⋅ N 1 − 1/ M 10 + 5/ M 11 + 1/ M 12 + L N ≤ L N + L N = L 2 N . In addition, each bin uses at most L M + 1 \frac{L}{M}+1 M L + 1 colors (the +1 term comes from the constraint that we must color the last received vertex). Therefore, LOC(M 2 M^2 M 2 ) uses at most ( L M + 1 ) ⋅ 2 N L ≤ 3 N M \left(\frac{L}{M}+1\right)\cdot\frac{2N}{L}\le\frac{3N}{M} ( M L + 1 ) ⋅ L 2 N ≤ M 3 N colors. □
The Grand Finale
We are now ready to prove our main theorem, stated as follows.
Theorem 1.3. For every fixed ε > 0 \varepsilon> 0 ε > 0 , there exists a polynomial-time deterministic online coloring algorithm that attains a competitive ratio of O ( n / ( log log n ) 2 − ε ) O\left(n/(\log\log n)^{2-\varepsilon}\right) O ( n / ( log log n ) 2 − ε ) .
We prove that our algorithm runs in polynomial time (Lemma 6.28), and then evaluate the performance of Kawarabayashi, Yoneda, and Yoneda’s algorithm [23 ] for M M M -colorable graphs (Theorem 6.29). Finally, we prove the main theorem.
Lemma 6.28. The proposed algorithm for the problem LOC(M 2 M^2 M 2 ) runs in polynomial time.
Proof. We assume that N N N is sufficiently large. First, we evaluate the time complexity of Algorithm 4 for solving CliqueFree(r r r ) (r ≤ M + 1 r \le M+1 r ≤ M + 1 ). In the algorithm for object coloring (Lemma 6.3), each set can be processed in O ( ∣ U ∣ ) O(|U|) O ( ∣ U ∣ ) time. In Algorithm 4, each bin has size n r ≤ L n_r \le L n r ≤ L , so the number of ( r − 2 ) (r-2) ( r − 2 ) -cliques in each bin is at most L r − 2 ≤ L M − 1 ≤ N L^{r-2}\le L^{M-1}\le N L r − 2 ≤ L M − 1 ≤ N , totaling at most N 2 N^2 N 2 across all bins. Hence, we can assume ∣ U ∣ ≤ N 2 |U|\le N^2 ∣ U ∣ ≤ N 2 , so Algorithm 4 runs in O ( N 2 M 2 ) O(N^2M^2) O ( N 2 M 2 ) time per vertex, excluding child instances; note that we find all these cliques in O ( N 2 M 2 ) O(N^2M^2) O ( N 2 M 2 ) time by brute force. Since the recursion depth is at most M M M , the total time for solving CliqueFree(r r r ), including recursion, is O ( N 2 M 3 ) O(N^2M^3) O ( N 2 M 3 ) time per vertex.
Next, we evaluate the time complexity for solving LOC(M 2 M^2 M 2 ).
The running time of Algorithm 6 excluding child instances is O ( N 3 ) O(N^{3}) O ( N 3 ) time per vertex, due to ∣ S ∣ ≤ N 2 |\mathcal{S}| \le N^{2} ∣ S ∣ ≤ N 2 (by the same discussion as ∣ U ∣ ≤ N 2 |\mathcal{U}| \le N^{2} ∣ U ∣ ≤ N 2 above) and at most N N N child instances are created due to ∣ Q 1 ∣ + ⋯ + ∣ Q t ∣ ≤ N |Q_{1}| + \cdots+ |Q_{t}| \le N ∣ Q 1 ∣ + ⋯ + ∣ Q t ∣ ≤ N .
The recursion depth for solving LOC(M 2 M^{2} M 2 ), excluding CliqueFree(⋅ \cdot ⋅ ) (but including child instances of LOC(⋅ \cdot ⋅ ), CB(⋅ , ⋅ \cdot,\cdot ⋅ , ⋅ )), is at most M ⋅ M 2 = M 3 M \cdot M^{2} = M^{3} M ⋅ M 2 = M 3 .
Therefore, the algorithm uses O ( max { N 2 M 3 , N 3 } ) ⋅ M 3 = O ( N 3 M 3 ) O(\max\{N^{2}M^{3}, N^{3}\}) \cdot M^{3} = O(N^{3}M^{3}) O ( max { N 2 M 3 , N 3 }) ⋅ M 3 = O ( N 3 M 3 ) time per vertex in total. This sums to O ( N 4 ( log log N ) 3 ( 1 − ε / 2 ) ) O(N^{4}(\log\log N)^{3(1-\varepsilon/2)}) O ( N 4 ( log log N ) 3 ( 1 − ε /2 ) ) time for all vertices. □
Theorem 6.29 ([KYY27]). There exists a polynomial-time deterministic online algorithm that colors N N N -vertex M M M -colorable graphs using O ( N / M 2 ) O(N/M^{2}) O ( N / M 2 ) colors.
Proof. By [23 Lemma 3.18] , for every k ≥ 0 k \ge0 k ≥ 0 , there is a polynomial-time deterministic algorithm to color N N N -vertex k k k -colorable graphs online using at most f ( k ) : = 2 2 k + 3 ⋅ N 1 − 1 k ( k − 1 ) / 2 + 1 f(k) := 2^{2^{k+3}} \cdot N^{1-\frac{1}{k(k-1)/2+1}} f ( k ) := 2 2 k + 3 ⋅ N 1 − k ( k − 1 ) /2 + 1 1 colors. Here,
log 2 f ( M ) = 2 M + 3 + ( 1 − 1 M ( M − 1 ) / 2 + 1 ) log 2 N = ( log N ) o ( 1 ) + log 2 N − Θ ( log N ( log log N ) 2 − ε ) = log 2 N − ω ( log log N ) . \log_{2} f(M) = 2^{M+3} + \left(1 - \frac{1}{M(M-1)/2+1}\right)\log_{2}N
= (\log N)^{o(1)} + \log_{2}N - \Theta\left(\frac{\log N}{(\log\log N)^{2-\varepsilon}}\right)
= \log_{2}N - \omega(\log\log N). log 2 f ( M ) = 2 M + 3 + ( 1 − M ( M − 1 ) /2 + 1 1 ) log 2 N = ( log N ) o ( 1 ) + log 2 N − Θ ( ( log log N ) 2 − ε log N ) = log 2 N − ω ( log log N ) .
Therefore, f ( M ) = O ( N / ( log N ) c ) f(M) = O(N/(\log N)^{c}) f ( M ) = O ( N / ( log N ) c ) for every fixed c > 0 c > 0 c > 0 , and Theorem 6.29 follows. □
Proof of Theorem 1.3. For every integer k ≥ 1 k \ge1 k ≥ 1 , there exists a polynomial-time deterministic algorithm that colors N N N -vertex k k k -colorable graphs online in k ⋅ O ( N / M 2 ) k \cdot O(N/M^{2}) k ⋅ O ( N / M 2 ) colors: we can use Theorem 6.29 for k ≤ M k \le M k ≤ M , we can use our algorithm for LOC(M 2 M^{2} M 2 ) for M < k ≤ M 2 M < k \le M^{2} M < k ≤ M 2 , and we can use distinct colors for all vertices for k > M 2 k > M^{2} k > M 2 (which uses N N N colors).
We note that LOC(M 2 M^{2} M 2 ) applies to M 2 M^{2} M 2 -colorable graphs, in which case the problem does not terminate. The algorithm for LOC(M 2 M^{2} M 2 ) runs in polynomial time by Lemma 6.28. Therefore, by Lemma 3.3 , we have a polynomial-time deterministic online coloring algorithm that attains a competitive ratio of O ( N / M 2 ) O(N/M^{2}) O ( N / M 2 ) , which is O ( N / ( log log N ) 2 − ε ) O(N/(\log\log N)^{2-\varepsilon}) O ( N / ( log log N ) 2 − ε ) . □
Conclusion
In this paper, we studied the competitive ratio of the online coloring problem. The best previous upper and lower bounds are shown in Table 1 ; large poly-logarithmic gaps remained for both randomized and deterministic algorithms. However, we have improved three of these results. In § 4 , we established the Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) lower bound for deterministic algorithms. In § 5 , we established the O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^{2}/\log^{2}n) O ( n ( log log n ) 2 / log 2 n ) upper bound for randomized algorithms. Finally, in § 6 , we established the O ( n / ( log log n ) 2 − ε ) O(n/(\log\log n)^{2-\varepsilon}) O ( n / ( log log n ) 2 − ε ) upper bound for deterministic algorithms.
Table 1. The improvements in upper bounds and lower bounds of competitive ratio for the online graph coloring problem.
As a result, we have nearly closed the gap for randomized algorithms, and the gap for deterministic algorithms has become significantly smaller. Most importantly, we finally affirmatively solved the 40-year-old open question of whether randomized algorithms are asymptotically better than deterministic algorithms. Since there exists an O ( n ( log log n ) 2 / log 2 n ) O(n(\log\log n)^2/\log^2 n) O ( n ( log log n ) 2 / log 2 n ) -competitive randomized algorithm while any deterministic algorithm is Ω ( n / log n ) \Omega(n/\log n) Ω ( n / log n ) -competitive, the answer to this question is yes. However, for the deterministic side, the gap is still poly-logarithmic. In addition, for the randomized side, the gap is almost closed but not completely closed. Therefore, it is natural to present the following conjectures:
Conjecture 7.1. Every deterministic online coloring algorithm is Ω ( n / log c n ) \Omega(n/\log^c n) Ω ( n / log c n ) -competitive for every fixed c > 0 c > 0 c > 0 .
Conjecture 7.2. There exists a randomized online coloring algorithm, against an oblivious adversary, that attains a competitive ratio of O ( n / log 2 n ) O(n/\log^2 n) O ( n / log 2 n ) .
Especially, for the gap in deterministic algorithms, we are currently leaning toward the lower-bound side; we believe no deterministic algorithm achieves a competitive ratio of O ( n / log n ) O(n/\log n) O ( n / log n ) . This is because our adversary framework in § 4 , which decides the base color after two vertices share the same online color, is still loose and restricted.
AI Usage Disclosure
We extensively used OpenAI’s large language model, GPT-6 Astra, during the proof exploration phase, in collaboration with the authors. For Theorem 1.1 and Theorem 1.2 , the AI initially tried to prove the theorem using the low-chromatic approach, which considers improvements on k k k -colorable graphs for constant k k k to achieve a better competitive ratio. This research direction is also historically popular, as seen in [29 , 21 , 23 ] . However, it failed.
Therefore, the human authors introduced a new research direction that considers the large-chromatic case, especially from the viewpoint of Proposition 1.4 . In particular, we posed a question: “Can we construct an algorithm where almost all colors are used on exactly three vertices?” With this new approach, the AI managed to generate the proof. However, we consider the essence of our contribution to be the new high-chromatic approach; for example, in § 4 , the new adversary model that replaces the transparent model is natural given the question of whether the adversary can force “at most two vertices per color”. For Theorem 1.2 and Theorem 1.3, the AI generated complicated and unnatural proofs, and we substantially simplified them.
This paper was written entirely by the human authors, based on discussions of the intuition behind the algorithm. The authors used OpenAI’s GPT models to polish the paper’s presentation. The authors take full responsibility for the correctness, content, and readability of the paper.