betaFeedback

WorksComputer Science

Online Graph Coloring with Random Arrivals

Abstract

We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming nn and kk are known in advance, we present a randomized exponential-time algorithm that colors any kk-colorable graph on nn vertices with O(k3log⁡2klog⁡4n)O(k^3 \log^2 k \log^4 n) colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed k≥3k \geq 3, and is better than a known lower bound of Ω(log⁡k−1n)Ω(\log^{k-1} n) colors under adversarial arrivals for all fixed k≥6k \geq 6. In addition, assuming nn is known in advance, we obtain a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}). For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of n1−εn^{1-\varepsilon} for all fixed ε>0\varepsilon > 0. Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.

Introduction

We study the online coloring problem, in which vertices are revealed one by one. When a vertex arrives, we must assign it a color immediately, before the next vertex arrives, so that its color differs from the colors of all its previously revealed neighbors. See Figure 1 for an example. This is one of the most extensively studied problems in online algorithms, alongside the kk-server problem, paging/caching, and online matching [4].

Figure 1. An example of online graph coloring. The numbers inside the vertices indicate their assigned colors. Vertices and edges drawn with gray dotted lines have not yet been revealed. The player must assign a color immediately when a vertex arrives.

Online Coloring

Online coloring is a classical problem for which natural algorithms are ineffective. The most intuitive strategy is First-Fit [11], which always chooses the smallest available color. However, First-Fit can use n/2n/2 colors even on an nn-vertex bipartite graph, as shown in Figure 2 (such graphs are called crown graphs1). Accordingly, online coloring has been widely studied since the 1980s [25]. The best-known upper bounds on the competitive ratio are as follows: O(nlog⁡n)O\left(\frac{n}{\log n}\right) for randomized algorithms by Halldórsson [13] [13], and O(nlog⁡log⁡n)O\left(\frac{n}{\log\log n}\right) for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda [22] [22]. In contrast, a lower bound of Ω(nlog⁡2n)\Omega\left(\frac{n}{\log^2 n}\right) is known due to Halldórsson and Szegedy [14] [14].

Figure 2. An nn-vertex bipartite graph on which First-Fit uses n/2n/2 colors.

Given these strong negative results, online coloring of kk-colorable graphs for a fixed k≥2k \ge2 has received attention. For bipartite graphs (k=2k = 2), a deterministic algorithm by Lovász, Saks, and Trotter [25] [25] achieves O(log⁡n)O(\log n) colors. The situation becomes much harder for k≥3k \ge3: even for k=3k = 3, the best-known results are a randomized O~(n1/2)\widetilde{O}(n^{1/2})-color algorithm by Vishwanathan [32] [32] and a deterministic O~(n2/3)\widetilde{O}(n^{2/3})-color algorithm by Kierstead [17] [17]. For comparison, the best-known lower bound is Ω(log⁡k−1n)\Omega(\log^{k-1} n) colors [32], leaving a substantial gap between the upper and lower bounds.

Online coloring is also studied for special graph classes, e.g., trees [6], interval graphs [20], planar graphs [15], bounded-treewidth graphs [5], and graphs of large odd girth [35]. See [16] for a survey on online coloring.

The Random-Order Model

The random-order model, which assumes that the input order is chosen uniformly at random, is widely studied in the context of online algorithms. The most well-known problem is arguably the secretary problem, in which nn candidates arrive for a job interview in random order, and the interviewer must decide immediately after each interview whether to hire the candidate. Only one candidate can be hired overall. Thanks to random arrivals, the classical secretary algorithm [23] selects the best candidate with probability at least 1e≈0.368\frac{1}{e} \approx0.368. In contrast, under an adversarial arrival order, no algorithm can guarantee a success probability greater than 1n\frac{1}{n}. The random-order model also leads to improved performance in many other online problems, including the following examples (see [12] for a survey):

  • For the online bipartite matching problem, the optimal (tight) randomized competitive ratio is 1−1e≈0.6321-\frac{1}{e} \approx0.632 under adversarial arrivals [21]. However, under the random-order model, an algorithm achieves a competitive ratio of 0.6960.696 [27].

  • For the online knapsack problem, no algorithm can achieve a bounded competitive ratio under adversarial arrivals. However, under the random-order model, an algorithm achieves a competitive ratio of 0.1530.153 [18].

Online Coloring. In online coloring with random arrivals, the given graph G=(V,E)G=(V,E) is fixed, and the arrival order of the nn vertices is chosen uniformly at random from the n!n! possibilities, each with probability 1n!\frac{1}{n!}. This setting has been particularly well-studied for First-Fit.

  • For trees, First-Fit uses Θ(log⁡n)\Theta(\log n) colors under adversarial arrivals [6, 11], but it drops to Θ(log⁡nlog⁡log⁡n)\Theta\left(\frac{\log n}{\log\log n}\right) colors in expectation under the random-order model [10, 7].

  • For crown graphs (Figure 2), First-Fit uses n/2n/2 colors under adversarial arrivals, but it drops to 2.5+O(1n)2.5+O\left(\frac{1}{n}\right) colors in expectation under the random-order model [34].

  • For general bipartite graphs, it was conjectured that First-Fit only uses polylogarithmic number of colors in the random-order model [7], but it is claimed to be disproved; a very recent preprint shows a lower bound of Ω(n1/2000)\Omega(n^{1/2000}) colors in expectation [24].

However, due to the inherent difficulty of online coloring, few studies have investigated random arrivals beyond First-Fit. In particular, it remained open whether algorithms for kk-colorable graphs could be improved under the random-order model; for example, whether an O(n1/2−ε)O(n^{1/2-\varepsilon})-color algorithm exists for 33-colorable graphs, which would improve upon the result of [32].

Our Contribution

In this paper, we show that the random-order model substantially improves the performance in online coloring: kk-colorable graphs can be colored online with a polylogarithmic number of colors for any constant kk. Formally, we prove the following main theorem.

Theorem 1. In the random-order model, when both nn and kk are known in advance, there exists a randomized online algorithm that colors any kk-colorable nn-vertex graph using O(k3log⁡2klog⁡4n)O(k^3 \log^2 k \log^4 n) colors in expectation.

This result significantly improves upon the previous O~(n1−1k−1)\widetilde{O}(n^{1-\frac{1}{k-1}})-color bound [32]. In addition, for all fixed k≥6k \ge6, our random-order result is better than the known lower bound of Ω(log⁡k−1n)\Omega(\log^{k-1} n) colors for adversarial arrivals [32]. Therefore, we establish the asymptotic separation between the random-order model and the adversarial-order model.

Moreover, assuming the result of the recent preprint [24], which claims that First-Fit uses expected Ω(n1/2000)\Omega(n^{1/2000}) colors for some bipartite graphs under random arrivals (and hence, for every k≥2k \ge2, some kk-colorable graphs), our algorithm asymptotically outperforms First-Fit for all k≥2k \ge2. Furthermore, we obtain a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}), as stated in the following theorem.

Theorem 2. In the random-order model, when nn is known in advance, there exists a randomized online algorithm that attains a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}).

Given the known lower bound of Ω(nlog⁡2n)\Omega\left(\frac{n}{\log^2 n}\right) on the competitive ratio for adversarial arrivals [14], this also establishes the asymptotic separation between the random-order model and the adversarial-order model in terms of the competitive ratio. Note that our result assumes that nn is known in advance. This is a standard assumption in the random-order model; several previous studies [2, 3, 23, 31] also make the same assumption.

Online Algorithms vs. Approximation Algorithms

A broader question in theoretical computer science concerns the relationship between the competitive ratio in online algorithms and the approximation ratio in polynomial-time approximation algorithms. This topic is discussed in various studies [19, 26]. In general, if an online algorithm achieves a performance guarantee beyond the hardness barrier for polynomial-time approximation algorithms, then it must run in super-polynomial time.

As a matter of fact, online algorithms can achieve better performance guarantees than approximation algorithms for some problems, although we did not find any references that explicitly mention this observation. The work of Rubinstein [29] [29] presents an O(log⁡n)O(\log n)-competitive algorithm for the (maximum cardinality) secretary problem on a downward-closed set system. This immediately yields an O(log⁡n)O(\log n)-competitive algorithm for “online maximum independent set” with random arrivals. In contrast, approximating (offline) maximum independent set within a factor of n1−εn^{1-\varepsilon} is NP-hard for every fixed ε>0\varepsilon> 0, as shown by Zuckerman [36] [36].

This paper gives an exponential-time O~(n2/3)\widetilde{O}(n^{2/3})-competitive algorithm for online coloring with random arrival order (Theorem 2), whereas approximating (offline) graph coloring within a factor of n1−εn^{1-\varepsilon} is NP-hard for every fixed ε>0\varepsilon> 0 [36]. Therefore, we establish the asymptotic separation between online and (deterministic or randomized) approximation algorithms in graph coloring, under the widely believed assumption that NP⊈BPP\mathrm{NP} \not\subseteq\mathrm{BPP} [1]. We note that, although a graph coloring can be obtained by repeatedly choosing a maximum independent set among the uncolored vertices, Rubinstein’s algorithm [29] does not directly imply an online coloring algorithm for random arrivals because the random arrival order on the uncolored vertices is not guaranteed.

Remark 3. Since the approximation side allows randomized algorithms, including random-order processing, we regard this comparison as fair. Moreover, our result achieves O(log⁡4n)O(\log^{4} n) colors for 3-colorable graphs; however, no polynomial-time algorithm that colors 3-colorable graphs with O(n1/10)O(n^{1/10}) colors is known at the time of writing.2

Overview of the Algorithm

In this subsection, we present an overview of our algorithm and the intuition behind using random arrival order. For simplicity, we consider the case k=3k = 3 here; the goal is to color a 3-colorable graph G=(V,E)G = (V, E) online with O(log⁡4n)O(\log^{4} n) colors.

First, it suffices to devise an algorithm that colors the last n/2n/2 vertices with O(log⁡3n)O(\log^{3} n) colors, using information from the first n/2n/2 vertices. If this can be done, we can color the entire graph with O(log⁡4n)O(\log^{4} n) colors by recursively applying the same algorithm to the first n/2n/2 vertices (for example, we color the n/4+1,…,n/2n/4 + 1, \ldots, n/2-th vertices using information from the first n/4n/4 vertices), using completely disjoint color sets for different levels of recursion. Here, we denote the set of the first n/2n/2 vertices by SS.

The Benefit of Random Order. The benefit of random arrival order is that S⊆VS \subseteq V can be assumed to be chosen uniformly at random. Hence, we can assume that the two parts, G[S]G[S] and G[V∖S]G[V \setminus S], have similar properties. For example, the sizes of maximum independent sets and the sizes of each color class in a 3-coloring φ:V→{1,2,3}\varphi: V \to\{1, 2, 3\} are very similar.

In particular, for a sufficiently large independent set I⊆VI \subseteq V, the parts of II that lie in SS and in V∖SV \setminus S do not differ much in size, with a statistical error of only ±O~(n)\pm\widetilde{O}(\sqrt{n}). Therefore, after the first n/2n/2 vertices have arrived, if we “sample” an independent set I⊆SI \subseteq S of G[S]G[S], then it is likely that II can be “extended” to the vertices in V∖SV \setminus S to the extent as large as II. This mechanism allows us to obtain a large independent set in G[V∖S]G[V \setminus S] online.

Hardcore Sampling and Extension. After receiving all vertices in SS, we sample an independent set I⊆SI \subseteq S from the hardcore model [9, 33] with parameter λ≈140ln⁡n\lambda\approx\frac{1}{40\ln n}, where II is chosen with probability proportional to λ∣I∣\lambda^{|I|}. As implied by the fact that a 3-colorable graph G[S]G[S] has an independent set of size at least ∣S∣/3≈n/6|S|/3 \approx n/6, the expected size of II is Θ(λn)=Θ(nlog⁡n)\Theta(\lambda n) = \Theta\left(\frac{n}{\log n}\right).

Then, the set of “eligible” vertices for extending the independent set II toward V∖SV \setminus S is J:={v∈V∖S:NI(v)=∅}J := \{v \in V \setminus S : N_I(v) = \emptyset\}, which is sufficiently large by the discussion above.3 While II itself may not be an independent set, it can be proven that G[J]G[J] most probably has maximum degree O(log⁡2n)O(\log^{2} n). See Figure 3 for an illustration. This implies that a large fraction of vertices in V∖SV \setminus S can be colored online using First-Fit with only O(log⁡2n)O(\log^2 n) colors.

Figure 3. Sampling an independent set from SS and attempting to extend it into V∖SV \setminus S.

Covering V∖SV \setminus S with Multiple Samples. The issue is that, with a single independent set II, only a fraction of the vertices in V∖SV \setminus S are colored. We address this issue by carefully sampling a sequence of independent sets I1,…,IrI_1,\ldots,I_r (Ir=∅I_r = \varnothing), where rr is most probably O(log⁡n)O(\log n). We also maintain “bins” J1,…,Jr⊆V∖SJ_1,\ldots,J_r \subseteq V \setminus S for the extension counterpart, initially empty. For each arrival of v∈V∖Sv \in V \setminus S, we find the smallest ii such that NIi(v)=∅N_{I_i}(v) = \varnothing, and put vv into JiJ_i. Then, we can prove that each G[Ji]G[J_i] most probably has maximum degree O(log⁡2n)O(\log^2 n). Hence, by applying First-Fit to each of G[J1],…,G[Jr]G[J_1],\ldots,G[J_r], using a separate set of colors for each bin, we can most probably color the entire V∖SV \setminus S with r⋅O(log⁡2n)=O(log⁡3n)r \cdot O(\log^2 n) = O(\log^3 n) colors.

Organization

§ 2 presents some formal definitions and notation. § 3 introduces the hardcore model and investigates its properties. § 4 introduces the main algorithm, and § 5 analyzes the number of colors used. § 6 presents an algorithm with a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}). Finally, § 7 concludes the paper and presents some conjectures.

Preliminaries

Before moving on to our algorithms, we present the required notation and definitions. First, we formally define online coloring with random arrival order. Then, we define First-Fit, the most straightforward strategy for online coloring.

Definition 4 (Online Coloring). In the online coloring problem, an undirected graph G=(V,E)G = (V, E) is initially empty; i.e., there are zero vertices. The vertices of GG are given one by one. Immediately after a vertex vv arrives (along with all edges incident to previously arrived vertices), we must assign a color c(v)∈Nc(v) \in\mathbb{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\}|.

Definition 5 (Random-Order Model). The random-order model of online coloring assumes that a graph G∗=(V∗,E∗)G^* = (V^*, E^*), where V∗={v1,…,vn}V^* = \{v_1,\ldots,v_n\}, is initially fixed and is hidden from the algorithm. We additionally assume that nn is known in advance. The vertices arrive in the order vσ(1),…,vσ(n)v_{\sigma(1)},\ldots,v_{\sigma(n)}, where

σ:{1,…,n}→{1,…,n}\sigma: \{1,\ldots,n\} \to\{1,\ldots,n\} is a permutation that is selected uniformly at random from n!n! possibilities, each with probability 1n!\frac{1}{n!}.

Definition 6 (First-Fit). First-Fit is an algorithm for online coloring that assigns each new vertex the smallest available color.

We use the following notation. Given a graph G=(V,E)G=(V,E), we denote the set of vertices adjacent to v∈Vv\in V as N(v)N(v), and the set of vertices adjacent to at least one vertex in S⊆VS\subseteq V as N(S)N(S). For a vertex set X⊆VX\subseteq V, we denote NX(v):=N(v)∩XN_X(v):=N(v)\cap X and NX(S):=N(S)∩XN_X(S):=N(S)\cap X. We denote the subgraph induced by S⊆VS\subseteq V as G[S]G[S]. We denote the chromatic number of GG as χ(G)\chi(G). We denote the set of all independent sets as I(G)\mathcal{I}(G). In O~\widetilde{O}-, Ω~\widetilde{\Omega}-, and Θ~\widetilde{\Theta}-notation, we write O~(f(n))\widetilde{O}(f(n)), Ω~(f(n))\widetilde{\Omega}(f(n)), and Θ~(f(n))\widetilde{\Theta}(f(n)) to hide polylogarithmic factors in f(n)f(n).

Hardcore Model

In this section, we discuss the properties of randomly sampled independent sets. We sample independent sets using the hardcore model [9, 33].

Definition 7 (Hardcore Model). Given a graph G=(V,E)G=(V,E), the hardcore model ISλ(G)\mathrm{IS}_{\lambda}(G) with parameter λ>0\lambda>0 is a probability distribution that chooses an independent set I∈I(G)I\in\mathcal{I}(G) with probability proportional to λ∣I∣\lambda^{|I|}. More precisely, define

Zλ(G):=∑I∈I(G)λ∣I∣.Z_{\lambda}(G):=\sum_{I\in\mathcal{I}(G)}\lambda^{|I|}.

Then, an independent set I∈I(G)I\in\mathcal{I}(G) is chosen with probability λ∣I∣Zλ(G)\frac{\lambda^{|I|}}{Z_{\lambda}(G)}. See Figure 4 for an example.

Figure 4. An example of the hardcore model, with the probability of selecting each independent set.

Basic Properties

First, we present some properties of the hardcore model that are used in the subsequent proofs.

Proposition 8. Let λ>0\lambda>0, and let G=(V,E)G=(V,E) be a kk-colorable graph. Then,

(1+λ)∣V∣/k≤Zλ(G)≤(1+λ)∣V∣.(1+\lambda)^{|V|/k}\leq Z_{\lambda}(G)\leq(1+\lambda)^{|V|}.

Proof. For the upper bound, Zλ(G)≤∑S⊆Vλ∣S∣=(1+λ)∣V∣Z_{\lambda}(G) \le\sum_{S\subseteq V} \lambda^{|S|} = (1+\lambda)^{|V|} by the binomial theorem. For the lower bound, since GG has a kk-coloring, one color class has size at least ∣V∣/k|V|/k, so it contains an independent set I′⊆VI' \subseteq V with ∣I′∣≥∣V∣/k|I'| \ge|V|/k. By the binomial theorem,

Zλ(G)≥∑I⊆I′λ∣I∣=(1+λ)∣I′∣≥(1+λ)∣V∣/k.Z_{\lambda}(G) \ge\sum_{I\subseteq I'} \lambda^{|I|} = (1+\lambda)^{|I'|} \ge(1+\lambda)^{|V|/k}.

Proposition 9. Let λ>0\lambda> 0, and let G=(V,E)G=(V,E) be a graph. For disjoint vertex sets S,T⊆VS,T\subseteq V (S∩T=∅S\cap T=\varnothing),

Zλ(G[S∪T])≤Zλ(G[S])⋅(1+λ)∣T∣.Z_{\lambda}(G[S\cup T]) \le Z_{\lambda}(G[S])\cdot(1+\lambda)^{|T|}.

Proof. Each I∈I(G[S∪T])I\in\mathcal{I}(G[S\cup T]) can be written as I=IS∪ITI=I_S\cup I_T, where IS∈I(G[S])I_S\in\mathcal{I}(G[S]) and IT∈I(G[T])I_T\in\mathcal{I}(G[T]). Therefore, Zλ(G[S∪T])≤Zλ(G[S])⋅Zλ(G[T])Z_{\lambda}(G[S\cup T])\le Z_{\lambda}(G[S])\cdot Z_{\lambda}(G[T]). By Proposition 8, we have Zλ(G[T])≤(1+λ)∣T∣Z_{\lambda}(G[T])\le(1+\lambda)^{|T|}, which proves the desired inequality.

The Size of Independent Sets

We analyze the expected size of an independent set. Note that the case λ=1\lambda=1 was already studied by Nilli [28] [28], who showed that the average size of independent sets for a kk-colorable graph is Ω(nklog⁡k)\Omega\left(\frac{n}{k\log k}\right) and proved that this bound is tight.

Lemma 10. Let λ∈(0,1]\lambda\in(0,1], and let G=(V,E)G=(V,E) be a kk-colorable graph. Then,

EI∼ISλ(G)[∣I∣]≥λ3kln⁡(3k)∣V∣.\mathbb{E}_{I\sim\mathrm{IS}_{\lambda}(G)}[|I|]\ge\frac{\lambda}{3k\ln(3k)}|V|.

Proof. First, the function f(x)=(13k)xf(x)=\left(\frac{1}{3k}\right)^x is convex, so it follows from Jensen’s inequality that:

(13k)E[∣I∣]≤E[(13k)∣I∣]\left(\frac{1}{3k}\right)^{\mathbb{E}[|I|]} \le\mathbb{E}\left[\left(\frac{1}{3k}\right)^{|I|}\right]
=1Zλ(G)(∑I∈I(G)(13k)∣I∣λ∣I∣)=Zλ/3k(G)Zλ(G)≤(1+λ/3k)∣V∣(1+λ)∣V∣/k.= \frac{1}{Z_{\lambda}(G)}\left(\sum_{I\in\mathcal{I}(G)}\left(\frac{1}{3k}\right)^{|I|}\lambda^{|I|}\right) = \frac{Z_{\lambda/3k}(G)}{Z_{\lambda}(G)} \le\frac{(1+\lambda/3k)^{|V|}}{(1+\lambda)^{|V|/k}}.

The last inequality is due to Proposition 8. Therefore:

E[∣I∣]≥−log⁡3k(1+λ/3k)∣V∣(1+λ)∣V∣/k\mathbb{E}[|I|]\ge-\log_{3k}\frac{(1+\lambda/3k)^{|V|}}{(1+\lambda)^{|V|/k}}
=1ln⁡(3k){∣V∣kln⁡(1+λ)−∣V∣ln⁡(1+λ3k)}= \frac{1}{\ln(3k)}\left\{\frac{|V|}{k}\ln(1+\lambda)-|V|\ln\left(1+\frac{\lambda}{3k}\right)\right\}
≥1ln⁡(3k){∣V∣k⋅23λ−∣V∣⋅λ3k}=λ3kln⁡(3k)∣V∣.\ge\frac{1}{\ln(3k)}\left\{\frac{|V|}{k}\cdot\frac{2}{3}\lambda-|V|\cdot\frac{\lambda}{3k}\right\} = \frac{\lambda}{3k\ln(3k)}|V|.

The last inequality follows from 23x≤ln⁡(1+x)≤x\frac{2}{3}x\le\ln(1+x)\le x for all x∈[0,1]x\in[0,1].

The Neighborhood Structures

We also investigate the structure surrounding a random independent set I∼IS⁡λ(G)I \sim\operatorname{IS}_{\lambda}(G). In the following two lemmas, we analyze the expected size of I∪N(I)I \cup N(I).

Lemma 11. Let λ>0\lambda> 0, and let G=(V,E)G = (V,E) be a graph. Then,

EI∼IS⁡λ(G)[∣I∣]=λ⋅EI∼IS⁡λ(G)[∣V∖(I∪N(I))∣].\mathbb{E}_{I\sim\operatorname{IS}_{\lambda}(G)}[|I|] = \lambda\cdot\mathbb{E}_{I\sim\operatorname{IS}_{\lambda}(G)}[|V \setminus(I \cup N(I))|].

Proof. Fix v∈Vv \in V. Let Ivin={I∈I:v∈I}\mathcal{I}^{\mathrm{in}}_v = \{I \in\mathcal{I} : v \in I\}, and Ivout={I∈I:v∈V∖(I∪N(I))}\mathcal{I}^{\mathrm{out}}_v = \{I \in\mathcal{I} : v \in V \setminus(I \cup N(I))\}. Then, the relationship Ivin={I∪{v}:I∈Ivout}\mathcal{I}^{\mathrm{in}}_v = \{I \cup\{v\} : I \in\mathcal{I}^{\mathrm{out}}_v\} holds (Figure 5), as shown below:

Figure 5. The definitions of Ivin\mathcal{I}^{\mathrm{in}}_v and Ivout\mathcal{I}^{\mathrm{out}}_v, and the bijection between them.

  • For every I∈IvoutI \in\mathcal{I}^{\mathrm{out}}_v, I∪{v}∈IvinI \cup\{v\} \in\mathcal{I}^{\mathrm{in}}_v because I∪{v}I \cup\{v\} is an independent set due to v∉I∪N(I)v \notin I \cup N(I).

  • For every I∪{v}∈IvinI \cup\{v\} \in\mathcal{I}^{\mathrm{in}}_v, I∈IvoutI \in\mathcal{I}^{\mathrm{out}}_v because II is an independent set and v∉N(I)v \notin N(I).

Here, for each I∈IvoutI \in\mathcal{I}^{\mathrm{out}}_v, the probability that I∪{v}I \cup\{v\} is chosen is λ\lambda times the probability that II is chosen. Therefore,

Pr⁡I∼IS⁡λ(G)[I∈Ivin]=λ⋅Pr⁡I∼IS⁡λ(G)[I∈Ivout](∀v∈V)\Pr_{I\sim\operatorname{IS}_{\lambda}(G)}[I \in\mathcal{I}^{\mathrm{in}}_v] = \lambda\cdot\Pr_{I\sim\operatorname{IS}_{\lambda}(G)}[I \in\mathcal{I}^{\mathrm{out}}_v] \quad(\forall v \in V)

Equivalently, Pr⁡I∼IS⁡λ(G)[v∈I]=λ⋅Pr⁡I∼IS⁡λ(G)[v∈V∖(I∪N(I))](∀v∈V)\Pr_{I\sim\operatorname{IS}_{\lambda}(G)}[v \in I] = \lambda\cdot\Pr_{I\sim\operatorname{IS}_{\lambda}(G)}[v \in V \setminus(I \cup N(I))] \quad(\forall v \in V)

Summing this equation over all v∈Vv \in V, we have EI∼IS⁡λ(G)[∣I∣]=λ⋅EI∼IS⁡λ(G)[∣V∖(I∪N(I))∣]\mathbb{E}_{I\sim\operatorname{IS}_{\lambda}(G)}[|I|] = \lambda\cdot\mathbb{E}_{I\sim\operatorname{IS}_{\lambda}(G)}[|V \setminus(I \cup N(I))|] by linearity of expectation. □\square

Lemma 12. Let λ∈(0,1]\lambda\in(0,1], and let G=(V,E)G = (V,E) be a kk-colorable graph. Then,

EI∼IS⁡λ(G)[∣I∪N(I)∣]≤(1−13kln⁡(3k))∣V∣.\mathbb{E}_{I\sim\operatorname{IS}_{\lambda}(G)}[|I \cup N(I)|] \le\left(1 - \frac{1}{3k\ln(3k)}\right)|V|.

Proof. By Lemma 11, E[∣V∖(I∪N(I))∣]=1λ⋅E[∣I∣]\mathbb{E}[|V \setminus(I \cup N(I))|] = \frac{1}{\lambda} \cdot\mathbb{E}[|I|]. Thus, by Lemma 10,

E[∣I∪N(I)∣]=∣V∣−1λ⋅E[∣I∣]≤∣V∣−1λ⋅λ3kln⁡(3k)∣V∣=(1−13kln⁡(3k))∣V∣.\begin{aligned} \mathbb{E}[|I \cup N(I)|] = |V| - \frac{1}{\lambda} \cdot\mathbb{E}[|I|] \\ &\le|V| - \frac{1}{\lambda} \cdot\frac{\lambda}{3k\ln(3k)}|V| = \left(1 - \frac{1}{3k\ln(3k)}\right)|V|. \end{aligned}

The Algorithm

We present an algorithm that colors kk-colorable graphs online with O(k3log⁡2klog⁡4n)O(k^3 \log^2 k \log^4 n) colors in the random-order model. The intuition is already given in Subsection 1.5. Note that, in the subsequent sections, we use G=(V,E)G=(V,E) to denote the current graph for the algorithm and G∗=(V∗,E∗)G^*=(V^*,E^*) to denote the final graph, as in Definition 5.

Basic Strategy

We consider developing an algorithm that colors the last n/2n/2 vertices using O(k3log⁡2klog⁡3n)O(k^3 \log^2 k \log^3 n) colors, given that the first n/2n/2 vertices have already arrived and have been colored. If this can be done, we can recursively apply the same algorithm to the first n/2n/2 vertices. Then, we can color the entire graph with O(k3log⁡2klog⁡4n)O(k^3 \log^2 k \log^4 n) colors.

However, for convenience in the analysis, we do not exactly divide them into n/2n/2 vertices each. Instead, we sample mm from a binomial distribution Binomial⁡(n,12)\operatorname{Binomial}(n,\frac{1}{2}), and we color the last n−mn-m vertices, given that the first mm vertices have already arrived. We note that mm is very close to n/2n/2 (with O~(n)\widetilde{O}(\sqrt{n}) error), so this does not fundamentally change the algorithm. We use disjoint colors for the first mm vertices and the last n−mn-m vertices. Let SS be the set of the first mm vertices. Under this framework, S⊆V∗S\subseteq V^* is uniformly distributed over the 2n2^n subsets of V∗V^*, as shown below.

Lemma 13. Let m∼Binomial⁡(n,12)m\sim\operatorname{Binomial}(n,\frac{1}{2}). Let SS be the set of the first mm vertices. Then, each subset of V∗V^* appears as SS with probability exactly 2−n2^{-n}.

Proof. The probability that ∣S∣=m|S|=m is 2−n⋅(nm)2^{-n}\cdot\binom{n}{m} by the binomial distribution. Also, there are (nm)\binom{n}{m} possible subsets of V∗V^* with size mm, and all of them have equal probabilities of appearing as SS because of the random-order model. Hence, Lemma 13 holds. □

Algorithm Details

Now, we consider an algorithm to color the last n−mn-m vertices V∗∖SV^*\setminus S. The algorithm consists of two phases: (1) the learning phase, which learns and extracts the structure of the first mm vertices, and (2) the output phase, which actually colors the last n−mn-m vertices by exploiting the learned structure. The two phases are described as follows.

(1) The Learning Phase. The core idea is that, if we sample an independent set I⊆SI\subseteq S, many vertices in V∗∖SV^*\setminus S are likely to have no neighbor in II thanks to the random arrivals (Subsection 1.5). Such a set of vertices can be colored efficiently, as we prove in § 5. However, a single sampled independent set II does not cover all vertices in V∗∖SV^*\setminus S. Therefore, we need to sample multiple independent sets.

In the algorithm, we sample a sequence of independent sets I1,I2,…I_1,I_2,\ldots, each from a hierarchy (S=A1⪰A2⪰⋯ )(S=A_1\succeq A_2\succeq\cdots). We start with A1=SA_1=S. For i=1,2,…i=1,2,\ldots in this order, we sample an independent set IiI_i from IS⁡λ[G[Ai]]\operatorname{IS}_{\lambda}[G[A_i]], and then we let Ai+1:=NAi(Ii)A_{i+1}:=N_{A_i}(I_i). See Figure 6 for an example. Eventually, IiI_i becomes empty; we let rr be the first index such that Ir=∅I_r=\varnothing. When coloring the remaining n−mn-m vertices, we use independent sets I1,…,IrI_1,\ldots,I_r. It can be proven that r=O(klog⁡klog⁡n)r=O(k\log k\log n) with high probability (Lemma 16), regardless of the value of the parameter λ∈(0,1]\lambda\in(0,1].

Figure 6. An example of the learning phase.

(2) The Output Phase. Next, we color the remaining n−mn-m vertices. Here, we maintain bins J1,…,Jr⊆V∗∖SJ_1,\ldots,J_r \subseteq V^* \setminus S, initially empty, which correspond to I1,…,IrI_1,\ldots,I_r, respectively.

When a vertex v∈V∗∖Sv \in V^* \setminus S arrives, we put vv into JiJ_i for the smallest ii such that NIi(v)=∅N_{I_i}(v)=\emptyset. Such an ii must exist because Ir=∅I_r=\emptyset. Although JiJ_i is not necessarily an independent set, it can be proven that the maximum degree of G∗[Ji]G^*[J_i] is O((klog⁡n)/λ)O((k\log n)/\lambda) with high probability in the range of i≤1λi \le\frac{1}{\lambda} (Lemma 21). Hence, with the parameter setting

λ:=16kln⁡(3k)ln⁡n+2,\lambda:= \frac{1}{6k\ln(3k)\ln n+2},

G∗[J1],…,G∗[Jr]G^*[J_1],\ldots,G^*[J_r] all have maximum degrees O(k2log⁡klog⁡2n)O(k^2\log k\log^2 n) with high probability (Lemma 22). Therefore, we can use the First-Fit algorithm to color each vertex of G∗[Ji]G^*[J_i]. We use disjoint sets of colors for bins J1,…,JrJ_1,\ldots,J_r.

Overall Algorithm. The pseudocode for the entire algorithm is presented in Algorithm 1. With high probability, we use O(k2log⁡klog⁡2n)O(k^2\log k\log^2 n) colors for each JiJ_i, and r=O(klog⁡klog⁡n)r=O(k\log k\log n). Therefore, we use O(k3log⁡2klog⁡3n)O(k^3\log^2 k\log^3 n) colors in expectation for the last n−mn-m vertices (Lemma 23). We analyze the algorithm’s performance in detail in the next section.

Remark 14. The runtime of Algorithm 1 is unbounded for the scenario where m=nm=n is chosen every time. However, if m=nm=n, the only thing that happens is a call to the identical procedure COLORING⁡k(n)\operatorname{COLORING}_k(n). Therefore, the outcome of Algorithm 1 remains the same if we choose mm from the distribution that excludes m=nm=n, i.e., each m=0,…,n−1m=0,\ldots,n-1 is chosen with probability 12n−1(nm)\frac{1}{2^{n-1}}{n \choose m}; this change makes its runtime bounded. Note that rr is also bounded; we will prove r≤n+1r\le n+1 in Lemma 15. Nevertheless, this algorithm runs in exponential time, because sampling an independent set from IS⁡λ(G[Ar])\operatorname{IS}_{\lambda}(G[A_r]) takes exponential time.

Analysis

In this section, we analyze the performance of Algorithm 1.

Number of Levels

First, we analyze the number rr of sampled independent sets: we prove that this is surely at most n+1n+1 and is O(klog⁡klog⁡n)O(k\log k\log n) with high probability.

Algorithm 1 COLORINGₖ(n): An algorithm to color an n-vertex graph online.
1: λ ← 1/(6k ln(3k) ln n + 2)
2: m ∼ Binomial(n, 1/2)
3: Color the first m vertices with COLORINGₖ(m), if m ≥ 1
4: S ← the set of the first m vertices
5: A₁ ← S; r ← 1
6: loop
7: Iᵣ ← IS_λ(G[Aᵣ])
8: if Iᵣ = ∅ then
9:   break
10: Aᵣ₊₁ ← N_{Aᵣ}(Iᵣ)
11: r ← r + 1
12: J₁, …, Jᵣ ← ∅
13: for each arrival of the remaining vertices v ∈ V* \ S do
14:   i ← the smallest i such that N_{Iᵢ}(v) = ∅
15:   Jᵢ ← Jᵢ ∪ {v}, and color v using First-Fit on G[Jᵢ]

Lemma 15. r≤n+1r \le n + 1.

Proof. Since Algorithm 1 ensures that I1,…,Ir−1≠∅I_1,\ldots,I_{r-1} \ne\varnothing and Ai+1=NAi(Ii)A_{i+1} = N_{A_i}(I_i) contains no vertex of IiI_i for each ii, it follows that A1⊋⋯⊋ArA_1 \supsetneq\cdots\supsetneq A_r. Since ∣A1∣≤n\lvert A_1\rvert\le n, we have r≤n+1r \le n + 1.

Lemma 16. Suppose that λ∈(0,1]\lambda\in(0,1]. For all possible inputs of the first mm vertices,

Pr⁡[r≤6kln⁡(3k)ln⁡n+2]≥1−1n.\Pr[r \le6k\ln(3k)\ln n + 2] \ge1 - \frac{1}{n}.

Proof. Fix an arbitrary realization of AiA_i. By applying Lemma 12 to G[Ai]G[A_i], we have

EI∼ISλ(G[Ai])[∣Ai+1∣]=EI∼ISλ(G[Ai])[∣NAi(I)∣]\mathbb{E}_{I\sim\mathrm{IS}_{\lambda}(G[A_i])}[\lvert A_{i+1}\rvert] = \mathbb{E}_{I\sim\mathrm{IS}_{\lambda}(G[A_i])}[\lvert N_{A_i}(I)\rvert]
≤EI∼ISλ(G[Ai])[∣I∪NAi(I)∣]\le \mathbb{E}_{I\sim\mathrm{IS}_{\lambda}(G[A_i])}[\lvert I\cup N_{A_i}(I)\rvert]
≤(1−13kln⁡(3k))∣Ai∣.\le \left(1-\frac{1}{3k\ln(3k)}\right)\lvert A_i\rvert.

Taking expectations over AiA_i, we obtain E[∣Ai+1∣]≤(1−13kln⁡(3k))E[∣Ai∣]\mathbb{E}[\lvert A_{i+1}\rvert]\le\left(1-\frac{1}{3k\ln(3k)}\right)\mathbb{E}[\lvert A_i\rvert]. Since ∣A1∣≤n\lvert A_1\rvert\le n,

E[∣Ai+1∣]≤(1−13kln⁡(3k))i⋅n.\mathbb{E}[\lvert A_{i+1}\rvert]\le\left(1-\frac{1}{3k\ln(3k)}\right)^i\cdot n.

Since (1−1x)x<1e\left(1-\frac{1}{x}\right)^x<\frac{1}{e} for all x≥1x\ge1, we have E[∣Ai∗+1∣]≤1n\mathbb{E}[\lvert A_{i^*+1}\rvert]\le\frac{1}{n} with i∗:=⌈3kln⁡(3k)⋅2ln⁡n⌉i^*:=\lceil3k\ln(3k)\cdot2\ln n\rceil. Since ∣Ai∗+1∣\lvert A_{i^*+1}\rvert is a non-negative integer, Markov’s inequality implies that Ai∗+1A_{i^*+1} is empty with probability at least 1−1n1-\frac{1}{n}. Moreover, if Ai∗+1A_{i^*+1} is empty, then Ii∗+1I_{i^*+1} is also empty, meaning that r≤i∗+1r\le i^*+1. Therefore, r≤6kln⁡(3k)ln⁡n+2r\le6k\ln(3k)\ln n+2 with probability at least 1−1n1-\frac{1}{n}.

Maximum Degrees

Next, we analyze the maximum degrees of the subgraphs G∗[Ji]G^{*}[J_i]. Specifically, we show that the maximum degrees of G∗[J1],…,G∗[Jr]G^{*}[J_1],\ldots,G^{*}[J_r] are O(k2log⁡klog⁡2n)O(k^2\log k\log^2 n) with high probability.

Introducing the History Sequence

Here, for a given graph G∗=(V∗,E∗)G^{*}=(V^{*},E^{*}), we need to analyze all possibilities for the first mm vertices and the sampled independent sets. The outcome of Algorithm 1 in terms of coloring the last n−mn-m vertices, i.e., J1,…,JrJ_1,\ldots,J_r, is determined by (A1,I1,…,Ar,Ir)(A_1,I_1,\ldots,A_r,I_r). To this end, we define history sequences as follows.

Definition 17 (History Sequence). Let t≥1t\ge1 be an integer. Given a graph G∗=(V∗,E∗)G^{*}=(V^{*},E^{*}), the “history sequence up to level tt” is defined as a sequence H:=(A1,I1,…,At,It)\mathcal{H}:=(A_1,I_1,\ldots,A_t,I_t). This is defined even when r<tr<t; in this case, Ai=Ii=∅A_i=I_i=\emptyset when i>ri>r. The set of all possible history sequences up to level tt is denoted as

Ht:={(A1,I1,…,At,It):A1⊆V∗, Ii∈I(G∗[Ai]) (1≤i≤t), Ai+1=NAi(Ii) (1≤i<t)}.\mathcal{H}_t:=\{(A_1,I_1,\ldots,A_t,I_t): A_1\subseteq V^{*},\ I_i\in\mathcal{I}(G^{*}[A_i])\ (1\le i\le t),\ A_{i+1}=N_{A_i}(I_i)\ (1\le i<t)\}.

It is easy to see that Ht\mathcal{H}_t indeed enumerates all history sequences with positive probability.

Proposition 18. Let t≥1t\ge1 be an integer. The probability that the history sequence up to level tt equals H=(A1,I1,…,At,It)∈Ht\mathcal{H}=(A_1,I_1,\ldots,A_t,I_t)\in\mathcal{H}_t is given by

p(H):=2−n⋅∏i=1tλ∣Ii∣Zλ(G∗[Ai]).p(\mathcal{H}):=2^{-n}\cdot\prod_{i=1}^{t}\frac{\lambda^{|I_i|}}{Z_{\lambda}(G^{*}[A_i])}.

Proof. The probability that S=A1S=A_1 is chosen is 2−n2^{-n} by Lemma 13. The probability that IiI_i is chosen from IS⁡λ(G∗[Ai])\operatorname{IS}_{\lambda}(G^{*}[A_i]) is λ∣Ii∣Zλ(G∗[Ai])\frac{\lambda^{|I_i|}}{Z_{\lambda}(G^{*}[A_i])} by the definition of the hardcore model (note that this probability is 1 for i>ri>r). Thus, Proposition 18 holds. □

Degree Analysis with Double-Counting Method

To establish the maximum degree bound, we prove the following lemma using the double-counting method on history sequences.

Lemma 19. Let λ>0\lambda>0 be the parameter of the hardcore model. Suppose G∗=(V∗,E∗)G^{*}=(V^{*},E^{*}) is a fixed kk-colorable graph. For every vertex v∈V∗v\in V^{*} and every integer t≥1t\ge1,

E[(1+λ(1+λ)t)∣N(v)∩Jt∣/k if v∈Jt, otherwise 0]≤1.\mathbb{E}\left[\left(1+\frac{\lambda}{(1+\lambda)^t}\right)^{|N(v)\cap J_t|/k}\ \text{if }v\in J_t,\ \text{otherwise }0\right]\le1.

Proof. Let H′⊆Ht\mathcal{H}'\subseteq\mathcal{H}_t be the set of all history sequences up to level tt in which the vertex vv is put into JtJ_t. For each H=(A1,I1,…,At,It)∈H′\mathcal{H}=(A_1,I_1,\ldots,A_t,I_t)\in\mathcal{H}', define the following:

  • Let X(H)⊆V∗X(\mathcal{H})\subseteq V^{*} be the set of vertices adjacent to vv in G∗[Jt]G^{*}[J_t].

  • Let Y(H)⊆V∗Y(\mathcal{H})\subseteq V^{*} be an arbitrary maximum independent set of G∗[X(H)]G^{*}[X(\mathcal{H})].

Since G∗[X(H)]G^*[X(\mathcal{H})] is kk-colorable, we have ∣Y(H)∣≥∣X(H)∣/k|Y(\mathcal{H})| \ge|X(\mathcal{H})|/k. Moreover, each subset W⊆Y(H)W \subseteq Y(\mathcal{H}) is also an independent set (see Figure 7). Therefore, we can write down 2∣Y(H)∣2^{|Y(\mathcal{H})|} history sequences as follows (we add WW to each of A1,…,AtA_1,\ldots,A_t and to ItI_t):

Figure 7. An illustration of the sets X(H)X(\mathcal{H}), Y(H)Y(\mathcal{H}), and W⊆Y(H)W \subseteq Y(\mathcal{H}) used to construct a new history sequence F(H,W)F(\mathcal{H}, W).

F(H,W):=(A1∪W,I1,…,At−1∪W,It−1,At∪W,It∪W),F(\mathcal{H}, W) := (A_1 \cup W, I_1, \ldots, A_{t-1} \cup W, I_{t-1}, A_t \cup W, I_t \cup W),

for each W⊆Y(H)W \subseteq Y(\mathcal{H}).

The sequence F(H,W)F(\mathcal{H}, W) is indeed a valid history sequence up to level tt. This can be shown as follows. First, for every i<ti<t, IiI_i is an independent set of G∗[Ai∪W]G^*[A_i \cup W], because IiI_i is an independent set of G∗[Ai]G^*[A_i]. Second, Ai+1∪W=NAi∪W(Ii)A_{i+1} \cup W = N_{A_i\cup W}(I_i) holds, because if some vertex w∈Ww \in W has no neighbor in IiI_i, then ww should have been put into bin JiJ_i instead of JtJ_t. Third, It∪WI_t \cup W is an independent set because W⊆Y(H)W \subseteq Y(\mathcal{H}) is an independent set and every vertex in W⊆JtW \subseteq J_t has no neighbor in ItI_t.

Next, the constructed histories F(H,W)F(\mathcal{H}, W), over all H∈H′\mathcal{H} \in\mathcal{H}' and W⊆Y(H)W \subseteq Y(\mathcal{H}), are pairwise distinct. This is because, from a history sequence F(H,W)=(A1′,I1′,…,At′,It′)F(\mathcal{H}, W) = (A'_1, I'_1, \ldots, A'_t, I'_t), we can uniquely recover WW as It′∩N(v)I'_t \cap N(v), and hence we can also uniquely recover the original history sequence H\mathcal{H}. The reason for W=It′∩N(v)W = I'_t \cap N(v) is that, for It′=It∪WI'_t = I_t \cup W, each vertex in ItI_t is not adjacent to vv (due to v∈Jtv \in J_t), but each vertex in WW is adjacent to vv (due to W⊆X(H)W \subseteq X(\mathcal{H})). Therefore, the total probability of all history sequences F(H,W)F(\mathcal{H}, W) is at most 1:

∑H∈H′∑W⊆Y(H)p(F(H,W))≤1.(1)\sum_{\mathcal{H}\in\mathcal{H}'} \sum_{W\subseteq Y(\mathcal{H})} p(F(\mathcal{H},W)) \le1. \tag*{(1)}

On the other hand, we also have a lower bound on the probability p(F(H,W))p(F(\mathcal{H}, W)) in terms of p(H)p(\mathcal{H}). This is calculated as follows:

p(F(H,W))=p(H)⋅λ∣W∣∏i=1t{Zλ(G∗[Ai∪W])/Zλ(G∗[Ai])}≥p(H)⋅λ∣W∣{(1+λ)∣W∣}t=p(H)⋅{λ(1+λ)t}∣W∣.\begin{aligned} p(F(\mathcal{H},W)) &= p(\mathcal{H}) \cdot\frac{\lambda^{|W|}}{\prod_{i=1}^{t}\{Z_\lambda(G^*[A_i \cup W])/Z_\lambda(G^*[A_i])\}} \\ &\ge p(\mathcal{H}) \cdot\frac{\lambda^{|W|}}{\{(1+\lambda)^{|W|}\}^{t}} \\ &= p(\mathcal{H}) \cdot\left\{\frac{\lambda}{(1+\lambda)^t}\right\}^{|W|}. \end{aligned}

The first equality is derived from Proposition 18, and the inequality is derived from Proposition 9. Therefore, by the binomial theorem, we obtain

∑W⊆Y(H)p(F(H,W))≥p(H)⋅{1+λ(1+λ)t}∣Y(H)∣.(2)\sum_{W\subseteq Y(\mathcal{H})} p(F(\mathcal{H},W)) \ge p(\mathcal{H}) \cdot\left\{1+\frac{\lambda}{(1+\lambda)^t}\right\}^{|Y(\mathcal{H})|}. \tag*{(2)}

Combining Equation (1), Equation (2), and ∣Y(H)∣≥∣X(H)∣/k|Y(\mathcal{H})| \ge|X(\mathcal{H})|/k, we obtain

∑H∈H′{p(H)⋅(1+λ(1+λ)t)∣X(H)∣/k}≤1.\sum_{\mathcal{H}\in\mathcal{H}'}\left\{p(\mathcal{H})\cdot\left(1+\frac{\lambda}{(1+\lambda)^t}\right)^{|X(\mathcal{H})|/k}\right\}\le1.

Lemma 19 follows directly from this inequality. □

Deriving the Degree Bound

Lemma 20. Let λ∈(0,1]\lambda\in(0,1] be the parameter of the hardcore model. Suppose G∗=(V∗,E∗)G^*=(V^*,E^*) is a fixed kk-colorable graph. For every vertex v∈V∗v\in V^* and every positive integer t≤1λt\le\frac{1}{\lambda},

Pr⁡[v∈Jt and ∣N(v)∩Jt∣≥10kln⁡nλ]≤1n3.(3)\Pr\left[v\in J_t\mathbin{\text{ and }}|N(v)\cap J_t|\ge\frac{10k\ln n}{\lambda}\right]\le\frac{1}{n^3}. \tag*{(3)}

Proof. First, for every positive integer t≤1λt\le\frac{1}{\lambda}, we have

λ(1+λ)t≥λ(1+λ)1/λ≥λe.\frac{\lambda}{(1+\lambda)^t}\ge\frac{\lambda}{(1+\lambda)^{1/\lambda}}\ge\frac{\lambda}{e}.

Therefore, Lemma 19 implies that the following inequality also holds for t≤1λt\le\frac{1}{\lambda}:

E[(1+λ/e)∣N(v)∩Jt∣/k if v∈Jt, otherwise 0]≤1.(4)\mathbb{E}\left[(1+\lambda/e)^{|N(v)\cap J_t|/k}\text{ if }v\in J_t,\text{ otherwise }0\right]\le1. \tag*{(4)}

By Markov’s inequality, Equation (4) implies Pr⁡[v∈Jt and (1+λ/e)∣N(v)∩Jt∣/k≥n3]≤1n3\Pr[v\in J_t\text{ and }(1+\lambda/e)^{|N(v)\cap J_t|/k}\ge n^3]\le\frac{1}{n^3}. By taking the logarithm of both sides, the condition above becomes

∣N(v)∩Jt∣≥3kln⁡nln⁡(1+λ/e).(5)|N(v)\cap J_t|\ge\frac{3k\ln n}{\ln(1+\lambda/e)}. \tag*{(5)}

Here,

3kln⁡nln⁡(1+λ/e)≤3kln⁡n(3/10)⋅λ=10kln⁡nλ.(6)\frac{3k\ln n}{\ln(1+\lambda/e)}\le\frac{3k\ln n}{(3/10)\cdot\lambda}=\frac{10k\ln n}{\lambda}. \tag*{(6)}

This is due to ln⁡(1+x/e)≥310x\ln(1+x/e)\ge\frac{3}{10}x for all x∈[0,1]x\in[0,1]. Therefore, combining Equation (5) and Equation (6), the probability that v∈Jtv\in J_t and ∣N(v)∩Jt∣≥10kln⁡nλ|N(v)\cap J_t|\ge\frac{10k\ln n}{\lambda} is at most 1n3\frac{1}{n^3}. □

Lemma 21. Let λ∈(0,1]\lambda\in(0,1] be the parameter of the hardcore model, and let t≤1λt\le\frac{1}{\lambda} be a positive integer. Suppose G∗=(V∗,E∗)G^*=(V^*,E^*) is a fixed kk-colorable graph. The probability that the maximum degree of G∗[Jt]G^*[J_t] exceeds 10kln⁡nλ\frac{10k\ln n}{\lambda} is at most 1n2\frac{1}{n^2}.

Proof. The maximum degree of G∗[Jt]G^*[J_t] exceeds 10kln⁡nλ\frac{10k\ln n}{\lambda} only if the event of Equation (3) occurs for at least one v∈V∗v\in V^*. Hence, by Lemma 20 and the union bound, this probability is at most 1n3⋅∣V∗∣=1n2\frac{1}{n^3}\cdot|V^*|=\frac{1}{n^2}. □

Lemma 22. With λ:=16kln⁡(3k)ln⁡n+2\lambda:=\frac{1}{6k\ln(3k)\ln n+2}, for every fixed kk-colorable graph G∗=(V∗,E∗)G^*=(V^*,E^*), G∗[J1],…,G∗[Jr]G^*[J_1],\ldots,G^*[J_r] all have maximum degrees at most 10kln⁡n⋅(6kln⁡(3k)ln⁡n+2)10k\ln n\cdot(6k\ln(3k)\ln n+2) with probability at least 1−3n1-\frac{3}{n}.

Proof. We apply Lemma 21 with parameter λ:=16kln⁡(3k)ln⁡n+2\lambda:=\frac{1}{6k\ln(3k)\ln n+2}. That is, for each t≤6kln⁡(3k)ln⁡n+2t\le6k\ln(3k)\ln n+2, the maximum degree of G∗[Jt]G^*[J_t] exceeds 10kln⁡n⋅(6kln⁡(3k)ln⁡n+2)10k\ln n\cdot(6k\ln(3k)\ln n+2) with probability at most 1n2\frac{1}{n^2}. Hence, the probability that both of the following conditions hold:

  • r≤6kln⁡(3k)ln⁡n+2r \le6k \ln(3k)\ln n + 2, and

  • at least one of G∗[J1],…,G∗[Jr]G^{*}[J_1],\ldots,G^{*}[J_r] has maximum degree more than 10kln⁡n⋅(6kln⁡(3k)ln⁡n+2)10k\ln n\cdot(6k\ln(3k)\ln n+2)

is at most n+1n2≤2n\frac{n+1}{n^2}\le\frac{2}{n} by the union bound and the fact that r≤n+1r\le n+1 (Lemma 15). Excluding the case r>6kln⁡(3k)ln⁡n+2r>6k\ln(3k)\ln n+2, which happens with probability at most 1n\frac{1}{n} (Lemma 16), Lemma 22 follows. □

The Grand Finale

Finally, we analyze the total number of colors used in Algorithm 1.

Lemma 23. In Algorithm 1, the number of colors used for V∗∖SV^{*}\setminus S is O(k3log⁡2klog⁡3n)O(k^{3}\log^{2}k\log^{3}n) in expectation.

Proof. If the maximum degrees in G[J1],…,G[Jr]G[J_1],\ldots,G[J_r] are at most Δ\Delta, then First-Fit uses at most Δ+1\Delta+1 colors, resulting in at most r(Δ+1)r(\Delta+1) colors for the entire V∗∖SV^{*}\setminus S. Therefore, by Lemma 16, Lemma 22, and the union bound, we use at most O(klog⁡klog⁡n)⋅O(k2log⁡klog⁡2n)=O(k3log⁡2klog⁡3n)O(k\log k\log n)\cdot O(k^{2}\log k\log^{2}n)=O(k^{3}\log^{2}k\log^{3}n) colors with probability at least 1−4n1-\frac{4}{n}. In the remaining case, which occurs with probability at most 4n\frac{4}{n}, we may use up to nn colors, but this is negligible. □

Lemma 24. The number of calls to COLORING⁡k(⋅)\operatorname{COLORING}_{k}(\cdot) in Algorithm 1 is at most 2log⁡2n+12\log_{2}n+1 with probability at least 1−1n1-\frac{1}{n}.

Proof. By Lemma 13, each vertex v∈V∗v\in V^{*} is put into SS, i.e., colored in the recursion, with probability 12\frac{1}{2}. Hence, each vertex v∈V∗v\in V^{*} goes down for at least 2log⁡2n2\log_{2}n recursions with probability at most 2−2log⁡2n=1n22^{-2\log_{2}n}=\frac{1}{n^{2}}. If this does not happen for any v∈V∗v\in V^{*}, then the recursion depth in Algorithm 1 is at most 2log⁡2n2\log_{2}n. By the union bound, this occurs with probability at least 1−1n2⋅∣V∗∣=1−1n1-\frac{1}{n^{2}}\cdot|V^{*}|=1-\frac{1}{n}. □

We are now ready to prove our main theorem, which shows that Algorithm 1 uses at most O(k3log⁡2klog⁡4n)O(k^{3}\log^{2}k\log^{4}n) colors in expectation.

Theorem 1 (restated). In the random-order model, when both nn and kk are known in advance, there exists a randomized online algorithm that colors any kk-colorable nn-vertex graph using O(k3log⁡2klog⁡4n)O(k^{3}\log^{2}k\log^{4}n) colors in expectation.

Proof. For each call to COLORING⁡k(⋅)\operatorname{COLORING}_{k}(\cdot), we use O(k3log⁡2klog⁡3n)O(k^{3}\log^{2}k\log^{3}n) colors in expectation, due to Lemma 23. Note that we can assume random arrivals in each call to COLORING⁡k(m)\operatorname{COLORING}_{k}(m), because mm does not depend on the graph structure (i.e., it depends only on random choices), and the probability of this event does not change by shuffling the order of the first mm vertices, due to the random-order assumption in the original graph G∗G^{*}.

Hence, across the shallowest ⌊2log⁡2n+1⌋\lfloor2\log_{2}n+1\rfloor calls to COLORING⁡k(⋅)\operatorname{COLORING}_{k}(\cdot) (or all calls if there are fewer), we use O(k3log⁡2klog⁡4n)O(k^{3}\log^{2}k\log^{4}n) colors in expectation. If there are more than 2log⁡2n+12\log_{2}n+1 calls, at most nn colors may be used, but this probability is at most 1n\frac{1}{n} (Lemma 24), so this is negligible. □

The Competitive Ratio

We consider online coloring with random arrivals for general graphs. In online coloring, a lower bound of Ω(nlog⁡2n)\Omega\left(\frac{n}{\log^2 n}\right) on the competitive ratio is known for both deterministic and randomized algorithms [14]. However, with the random-order model, we can do better.

Theorem 2 (restated). In the random-order model, when nn is known in advance, there exists a randomized online algorithm that attains a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}).

Proof. The idea is to simulate the behavior of Algorithm 1 for 2q2^q-colorable graphs, COLORING⁡2q(n)\operatorname{COLORING}_{2^q}(n), on the same input graph GG, for each q=0,1,…,⌈log⁡2n⌉q = 0,1,\ldots,\lceil\log_2 n\rceil in parallel processes. We assume disjoint sets of colors for different processes. For each arrival of vertex v∈Vv \in V, we color vv using the color selected by the process that has used the fewest colors so far.

We now analyze the number of colors used. Let q∗:=⌈log⁡2χ(G∗)⌉q^* := \lceil\log_2 \chi(G^*)\rceil. Since G∗G^* is 2q∗2^{q^*}-colorable, by Theorem 1, the number of colors used by the process with q=q∗q=q^*, denoted by cq∗c_{q^*}, satisfies

E[cq∗]=O((2q∗)3log⁡2(2q∗)log⁡4n)=O(χ(G∗)3log⁡2χ(G∗)log⁡4n).\mathbb{E}[c_{q^*}] = O\left((2^{q^*})^3\log^2(2^{q^*})\log^4 n\right) = O\left(\chi(G^*)^3\log^2\chi(G^*)\log^4 n\right).

Moreover, for each process, at most cq∗c_{q^*} colors are used in the actual online coloring, so the number of colors used overall is at most cq∗(⌈log⁡2n⌉+1)c_{q^*}(\lceil\log_2 n\rceil+1). Therefore, this algorithm uses O(χ(G∗)3log⁡2χ(G∗)log⁡5n)O(\chi(G^*)^3\log^2\chi(G^*)\log^5 n) colors in expectation. Also, it is obvious that we use at most nn colors. Thus, we attain a competitive ratio of O(n2/3log⁡7/3n)O(n^{2/3}\log^{7/3}n), with the worst-case bound attained when

χ(G∗)=Θ(n1/3log⁡7/3n).\chi(G^*) = \Theta\left(\frac{n^{1/3}}{\log^{7/3}n}\right).

Conclusion

In this paper, we presented an algorithm for online coloring with random arrivals that uses O(k3log⁡2klog⁡4n)O(k^3\log^2 k\log^4 n) colors for kk-colorable graphs. For online coloring as a whole, we improved the performance for the case k=3k=3 from O~(n1/2)\widetilde{O}(n^{1/2}) colors [32] to O(log⁡4n)O(\log^4 n) colors. We also achieved a competitive ratio of O~(n2/3)\widetilde{O}(n^{2/3}), which is better than the conventional lower bound Ω(nlog⁡2n)\Omega\left(\frac{n}{\log^2 n}\right) [14] and is better than an Ω(n1−ε)\Omega(n^{1-\varepsilon}) inapproximability bound for graph coloring [36]. These results demonstrate that the random-order model unlocks new possibilities for improving the performance of online coloring algorithms. It is now natural to pose the following conjectures.

Conjecture 25. In the random-order model, when both nn and kk are known in advance, there exists a randomized online algorithm that colors any kk-colorable nn-vertex graph using O(klog⁡n)O(k\log n) colors in expectation.

Conjecture 26. In the random-order model, when nn is known in advance, there exists a randomized online algorithm that attains a competitive ratio of O(log⁡n)O(\log n).

Finally, a limitation of our result is that it relies on the random-order model and does not extend to adversarial arrivals. It is natural to ask whether the following conjecture holds.

Conjecture 27. For any constant k≥3k \ge3, there exists a (randomized) online algorithm for coloring kk-colorable graphs with no(1)n^{o(1)} colors, even without assuming random arrivals.

Acknowledgements

We are grateful to our professor Ken-ichi Kawarabayashi for helpful discussions and comments. We also thank Yuta Inoue for his feedback on the Introduction section.

AI Usage Disclosure

The authors substantially used OpenAI’s large language model, GPT-6 Astra, during the proof exploration phase. Through an iterative process with the authors, the model generated the proof of the main theorem (Theorem 1) for the special case k=3k = 3. Then, the authors simplified the proof, discussed and obtained the intuition behind the algorithm, and generalized the analysis to all k≥3k \ge3. The authors also used GPT-6 Astra and GPT-5.6 Sol to polish the paper’s presentation. The authors take full responsibility for the correctness and content of the paper.

References

  1. [1]Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press Cambridge, 2009.
  2. [2]Susanne Albers and Maximilian Janke. “Scheduling in the Secretary Model”. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Vol. 213. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 6:1–6:22. DOI: 10.4230/LIPIcs.FSTTCS.2021.6.DOI
  3. [3]Susanne Albers, Arindam Khan, and Leon Ladewig. “Improved Online Algorithms for Knapsack and GAP in the Random Order Model”. In: Algorithmica 83.6 (2021), pp. 1750–1785. DOI: 10.1007/s00453-021-00801-2.DOI
  4. [4]Susanne Albers. “Online algorithms: a survey”. In: Mathematical Programming 97.1 (2003), pp. 3–26.DOI
  5. [5]Susanne Albers and Sebastian Schraink. “Tight bounds for online coloring of basic graph classes”. In: Algorithmica 83.1 (2021), pp. 337–360.arxiv.org/abs/1702.07172
  6. [6]Dwight R Bean. “Effective coloration”. In: The Journal of Symbolic Logic 41.2 (1976), pp. 469–480.DOI
  7. [7]Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło. “First-Fit Coloring of Forests in Random Arrival Model”. In: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Ed. by Rastislav Královič and Antonín Kučera. Vol. 306. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 33:1–33:10. ISBN: 978-3-95977-335-5. DOI: 10.4230/LIPIcs.MFCS.2024.33. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.33.DOI
  8. [8]Nikhil Bansal, Neng Huang, and Euiwoong Lee. Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs. 2026. arXiv: 2602.05904. URL: https://arxiv.org/abs/2602.05904.
  9. [9]Ewan Davies and Ross J Kang. The hard-core model in graph theory. 2025. arXiv: 2501.03379. URL: https://arxiv.org/abs/2501.03379.
  10. [10]Fabian Frei, Matthias Gehnen, Dennis Komm, Rastislav Královič, Richard Královič, Peter Rossmanith, and Moritz Stocker. Tree coloring: Random order and predictions. 2024. arXiv: 2405.18151. URL: https://arxiv.org/abs/2405.18151.
  11. [11]András Gyárfás and Jenő Lehel. “On-line and first fit colorings of graphs”. In: Journal of Graph Theory 12.2 (1988), pp. 217–227.DOI
  12. [12]Anupam Gupta and Sahil Singla. “Random-Order Models”. In: Beyond the Worst-Case Analysis of Algorithms. Ed. by Tim Roughgarden. Cambridge University Press, 2021, pp. 234–258. doi: 10.1017/9781108637435.015.DOI
  13. [13]Magnús M Halldórsson. “Parallel and On-Line Graph Coloring”. In: Journal of Algorithms 23.2 (1997), pp. 265–280. issn: 0196-6774. doi: 10.1006/jagm.1996.0836. URL: https://www.sciencedirect.com/science/article/pii/S0196677496908366.DOI
  14. [14]Magnús M Halldórsson and Mario Szegedy. “Lower bounds for on-line graph coloring”. In: Theoretical Computer Science 130.1 (1994), pp. 163–174. doi: 10.1016/0304-3975(94)90157-0.
  15. [15]Sandy Irani. “Coloring inductive graphs on-line”. In: Algorithmica 11.1 (1994), pp. 53–72.
  16. [16]Hal A Kierstead. “Coloring graphs on-line”. In: Online algorithms: the state of the art. Springer, 2005, pp. 281–305.
  17. [17]Henry A Kierstead. “On-line coloring k-colorable graphs”. In: Israel Journal of Mathematics 105.1 (1998), pp. 93–104.
  18. [18]Max Klimm and Martin Knaack. “Generalized assignment and knapsack problems in the random-order model”. In: Mathematical Programming (2026). doi: 10.1007/s10107-026-02405-6.DOI
  19. [19]Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. “Playing games with approximation algorithms”. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007, pp. 546–555.
  20. [20]Henry A Kierstead and William T Trotter. “An extremal problem in recursive combinatorics”. In: Congressus Numerantium 33 (1981), pp. 143–153.
  21. [21]Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. “An optimal algorithm for on-line bipartite matching”. In: Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990, pp. 352–358.DOI
  22. [22]Ken-ichi Kawarabayashi, Hirotaka Yoneda, and Masataka Yoneda. Online Graph Coloring for k-Colorable Graphs. 2025. arXiv: 2511.16100 [cs.DS]. URL: https://arxiv.org/abs/2511.16100.
  23. [23]Denis V Lindley. “Dynamic programming and decision theory”. In: Journal of the Royal Statistical Society: Series C (Applied Statistics) 10.1 (1961), pp. 39–51.DOI
  24. [24]Yaqiao Li and Xin Li. FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model. 2026. arXiv: 2610.15468 [cs.DS]. URL: https://arxiv.org/abs/2610.15468.
  25. [25]László Lovász, Michael Saks, and William T. Trotter. “An on-line graph coloring algorithm with sublinear performance ratio”. In: Discrete Mathematics 75.1–3 (1989), pp. 319–325.
  26. [26]Esther Mohr, Iftikhar Ahmad, and Günter Schmidt. “Online algorithms for conversion problems: a survey”. In: Surveys in Operations Research and Management Science 19.2 (2014), pp. 87–104.
  27. [27]Mohammad Mahdian and Qiqi Yan. “Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs”. In: Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011, pp. 597–606.
  28. [28]Alon Nilli. “The average size of an independent set in graphs with a given chromatic number”. In: Journal of Combinatorial Theory, Series B 45.1 (1988), pp. 112–114.
  29. [29]Aviad Rubinstein. “Beyond matroids: Secretary problem and prophet inequality with general constraints”. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016, pp. 324–332.arxiv.org/abs/1604.00357
  30. [30]Zhao Song. An O(n^{1/6})-Coloring Algorithm for 3-Colorable Graphs. SSRN working paper. 2026. DOI: 10.2139/ssrn.7551399. URL: https://ssrn.com/abstract=7551399.DOI
  31. [31]Richard Santiago, Ivan Sergeev, and Rico Zenklusen. “Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid”. In: Mathematical Programming 210.1–2 (2025), pp. 815–846. DOI: 10.1007/s10107-024-02177-x.DOI
  32. [32]Sundar Vishwanathan. “Randomized online graph coloring”. In: Journal of Algorithms 13.4 (1992), pp. 657–669.
  33. [33]Dror Weitz. “Counting independent sets up to the tree threshold”. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006, pp. 140–149.DOI
  34. [34]Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, and Yaqiao Li. FirstFit online coloring in the random order model. 2026. arXiv: 2608.29603. URL: https://arxiv.org/abs/2608.29603.
  35. [35]Hirotaka Yoneda and Masataka Yoneda. “Online Coloring for Graphs of Large Odd Girth”. In: 34th Annual European Symposium on Algorithms (ESA 2026). 2026, 127:1–127:15.
  36. [36]David Zuckerman. “Linear degree extractors and the inapproximability of max clique and chromatic number”. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006, pp. 681–690.

Paper details

vlnc:W_r4quqzq6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

GPT-6 Astra (bare), GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents