betaFeedback

WorksComputer Science

New bounds for online coloring three-colorable graphs

Abstract

We prove new lower and upper bounds for online coloring of three-colorable graphs, improving classical bounds of Vishwanathan [FOCS'1990] that have stood for more than three decades. For the lower bound against deterministic algorithms, we improve Vishwanathan's Ω(log⁡2n)Ω(\log^2n) to exp⁡ ⁣(Ω((log⁡n)1/3(log⁡log⁡n)2/3))\exp\!\bigl(Ω((\log n)^{1/3}(\log\log n)^{2/3})\bigr). For the upper bound of randomized algorithms, we give a randomized algorithm that achieves O(n)O(\sqrt{n}) improving Vishwanathan's O(nlog⁡n)O(\sqrt{n \log n}). Technically, for the lower bound construction, we introduce the language of tt-fold coloring for simpler description of recursive construction, and the notion of post-degree for future control, and use the flexibility of two-sided colors of bipartite graph, constructed using the independent set amplification method of Vishwanathan, as building blocks to ensure three-colorability. The randomized algorithm integrates, in a new way, some of the ideas in offline coloring of Wigderson and Blum with ideas of Vishwanathan in the online setting, such as the degree control from Wigderson, the offline-monochromatic class from Blum, and the anchor-sampling from Vishwanathan and the CBIP algorithm by Lov{á}sz, Saks and Trotter.

Introduction

Three-colorable graphs are computationally complicated objects: up to today, there is still no efficient algorithm to decide whether a given graph is three-colorable, in fact this is one formulation of the P vs NP problem. Besides computation, another perspective to study them is via information: how limited information inhibits the coloring even the computational time is allowed to be super-polynomial.

One model of studying limited information is the online graph vertex-coloring model. An online vertex-coloring algorithm receives vertices one at a time, together with their edges to earlier vertices. It must assign each vertex a color immediately and irrevocably. For a graph GG, an order π\pi, and an algorithm A\mathcal{A}, write CA(G,π)C_{\mathcal{A}}(G,\pi) for the number of colors used. In 1990, Vishwanathan [12] proved that every deterministic online algorithm requires Ω(log⁡2n)\Omega(\log^{2} n) colors to color three-colorable graphs on nn vertices, and gave a randomized algorithm that uses O(nlog⁡n)O(\sqrt{n}\log n) colors in expectation. These two bounds stood for more than three decades. This work improve both.

Theorem 1.1 (Deterministic lower bound). There is an absolute constant c>0c > 0 such that, for every sufficiently large nn and every deterministic online coloring algorithm A\mathcal{A}, some ordered three-colorable graph GG on nn vertices satisfies

CA(G,π)≥2c(log⁡n)1/3(log⁡log⁡n)2/3.C_{\mathcal{A}}(G,\pi) \ge2^{c(\log n)^{1/3}(\log\log n)^{2/3}}.

Theorem 1.2 (Randomized upper bound). There is a randomized online algorithm A\mathcal{A} such that, for every fixed ordered three-colorable graph with at most nn vertices,

ECA(G,π)=O(n).\mathbb{E}C_{\mathcal{A}}(G,\pi) = O(\sqrt{n}).

The algorithm can be implemented in expected polynomial time.

Remark 1.3. 1. By a technique introduced in Lovasz et al [11], one can assume online algorithms know the number of vertices, with only Θ(1)\Theta(1) multiplicative difference in the colors used. So we assume this when it is convenient. In particular, this implies the lower bound holds even if algorithms know nn.

  1. The lower bound Theorem 1.1 can be extended to work against randomized algorithms, and the randomized algorithm Theorem 1.2 can be adapted to give a deterministic algorithm in the random order model with the same bound: these are provided in the appendix.

  1. As in Vishwanathan [12], the two bounds we obtained could be generalized to get new bounds for online coloring on kk-colorable graphs for k≥4k \ge4. We did not try to do that.

Closely related work

Offline coloring three-colorable graphs: Wigderson and Blum. Wigderson’s O(n)O(\sqrt{n})-color algorithm [13] used two facts: the neighbourhood of a vertex in a three-colorable graph is bipartite, and a graph of maximum degree Δ\Delta admits a greedy (Δ+1)(\Delta+ 1)-coloring. Wigderson’s algorithm then proceeded by checking vertex degree: for degree at least n\sqrt{n}, it two-colored its neighborhood of at least n\sqrt{n} vertices and removed the neighborhood. There were at most n\sqrt{n} such removals. The remaining graph had degree below n\sqrt{n} and was colored greedily.

Blum [3] obtained O(n3/8polylog⁡n)O(n^{3/8}\operatorname{polylog} n) colors through several forms of combinatorial progress that he initiated and became a foundational framework for subsequent studies. One was to certify vertices that have the same color in every proper three-coloring and contract them, reducing the graph size. A collection of vertices certified in this way can be compressed into a single vertex. We call such a collection an offline-monochromatic class. For example, if uvuv is an edge, then all vertices incident to both uu and vv enjoy this property. This was one component of Blum’s framework, alongside independent-set and neighborhood arguments. Later offline algorithms combined combinatorial progress with semidefinite methods; examples included Blum–Karger [BK97] and Kawarabayashi–Thorup–Yoneda [8].

Some parts of Wigderson’s method were adapted to the online setting by Vishwanathan [12]. We use that too. Furthermore, we adapt Blum’s offline-monochromatic class compression into the online setting, suitably combined with a degree-control.

Online coloring bipartite graphs: FirstFit and CBIP. The algorithm FirstFit assigns the least positive integer absent from the earlier neighbors’ colors. Gyárfás and Lehel [5] studied FirstFit online coloring on restricted graph classes, in particular, they gave an online nn-vertex forest (hence, bipartite) construction forcing Ω(log⁡n)\Omega(\log n) colors on every deterministic algorithm.

It is not hard to see that FirstFit can use up to Θ(n)\Theta(n) colors on bipartite graphs of nn vertices, such as on crown graphs, see Y et al. [XYW+26]. However, a useful feature of FirstFit is that if it uses color kk on an online vertex vv, it is guaranteed that there are at least k−1k-1 vertices arrived before vv that are all connected to vv and exhausted the colors {1,…,k−1}\{1,\ldots,k-1\}.

Lovász, Saks, and Trotter [11] gave an online coloring algorithm, which became known as CBIP, using at most 2log⁡n+O(1)2\log n+O(1) colors for bipartite graphs on nn vertices. For the arriving vertex, the algorithm CBIP took the least color absent from the opposite side of its current connected component. Bianchi et al. [1] gave a component-growth proof of this upper bound and improved the bipartite lower bound. Gutowski et al. [4] proved the matching lower bound 2log⁡n−O(1)2\log n-O(1). Their construction explicitly tracked two-sided colors, namely colors appearing on both sides of a bipartite component. Li et al. [10] further gave a refined analysis of CBIP and two-sided colors, obtaining a 2κ2\kappa bound when at most κ\kappa connected components are present at any time.

In our lower-bound construction for three-colorable graphs, we construct bipartite graphs whose colors of interest are two-sided, and use these bipartite graphs as building blocks to construct larger graphs whose three-colorability is ensured by the flexibility of two-sided colors of the bipartite graphs, while forcing new online colors. In our randomized online algorithm design, we take advantage of the feature of FirstFit discussed above and the fact that CBIP uses Θ(log⁡n)\Theta(\log n) colors on bipartite graphs: both were already used by Vishwanathan [12].

Vishwanathan’s online lower and upper bounds on three-colorable graphs. Vishwanathan [12] gave an Ω(log⁡2n)\Omega(\log^2 n) lower bound and an O(nlog⁡n)O(\sqrt{n}\log n) randomized upper bound for three-colorable graphs; see also Kierstead’s survey [6].

For the lower bound, observe that it is equivalent to construct an independent set (of a three-colorable graph) that is forced to use lots of colors: this is because the whole graph can be decomposed into at most three independent sets. The core of Vishwanathan’s lower bound construction might be called independent set amplification, as illustrated in Figure 1. Suppose a construction produces an independent set AA with at least kk online colors. Construct a disjoint copy with such a set BB. Next construct a bipartite graph HH, joining all its vertices to AA. One of two parts of HH, say CC, has Ω(log⁡m)\Omega(\log m) colors on an mm-vertex bipartite construction. Note that colors used on CC is necessarily disjoint from colors used on AA. A simple calculation shows that either the independent set A∪BA \cup B or B∪CB \cup C has at least k+Ω(log⁡m)k + \Omega(\log m) colors. This amplification process can then be repeated within certain range of the related parameters, forcing at least Ω(log⁡2n)\Omega(\log^2 n) colors. This technique is also used in our lower bound construction.

Independent set amplification in Vishwanathan’s lower-bound construction

Figure 1. The independent set amplification in Vishwanathan’s lower-bound construction: either A∪BA \cup B or B∪CB \cup C forces Ω(log⁡m)\Omega(\log m) new online colors if ∣V(H)∣=m|V(H)| = m.

For the upper bound, it could be helpful to think of it as a randomized online version of Wigderson’s offline algorithm, see Figure 2 for an illustration. The algorithm reserved a separate palette of cc FirstFit colors. At the start it chose an index JJ uniformly from [c][c]. For each arriving online vertex the algorithm tried to color it using FirstFit with at most cc colors. In case when an online vertex vv needed to use color c+1c + 1 by FirstFit, the feature of FirstFit guaranteed a neighbor uu of vv in the color class JJ. The vertex uu was then used as an anchor and vv was colored by CBIP in the bipartite neighborhood of uu, using at most O(log⁡n)O(\log n) colors. Each anchor uu used a separate palette of at most O(log⁡n)O(\log n) colors. Since the expected size of the vertices in JJ was at most n/cn/c, the total colors was at most

Figure 2. Vishwanathan’s randomized algorithm.

c+O((n/c)log⁡n)=O(nlog⁡n)for c=Θ(nlog⁡n).c + O((n/c)\log n) = O(\sqrt{n\log n}) \quad\text{for } c = \Theta(\sqrt{n\log n}).

Note that the expected number of anchors was n/c=O(n/log⁡n)n/c = O(\sqrt{n/\log n}). Like Wigderson’s algorithm, this exploited bipartite neighborhoods; the logarithmic online cost replaced offline two-coloring.

For comparison, on the deterministic upper-bound side, Kierstead [7] gave O(n2/3(log⁡n)1/3)O(n^{2/3}(\log n)^{1/3}) colors for three-colorable graphs. For kk-colorable graphs with k≥4k \ge4,

Kierstead [7] also obtained upper bounds which were improved in the recent breakthrough Kawarabayashi, Yoneda, and Yoneda [9].

Conceptual and technical contributions

Deterministic lower bound. Our lower bound construction uses the similar independent set amplification as in Vishwanathan. A conceptually new way of doing the construction is that we use a tt-fold online coloring model: each vertex is assigned a set of tt distinct colors, and distinct vertices use disjoint color sets. The standard online coloring model corresponds to t=1t = 1. Suppose our goal is to force KK colors, we can trivially force it using a single vertex in the KK-fold coloring model, and then our task is to ask whether it is possible to force KK colors in the standard 1-fold coloring and using how many vertices. This suggests interpolation and simulation: if one can force KK colors using qq-fold coloring and NN vertices, given t<qt < q, can you simulate it (i.e., also force KK colors) using tt-fold coloring and N′N' vertices for some N′N' as a function of KK, NN, qq, tt? Clearly, such a simulation lemma can then be used to build a lower bound construction.

Hence, fixing KK, the goal is to upper bound N′N' as a function of KK, NN, qq, tt. It turns out that a certain control of the future is helpful. We use post-degree to control the future: the post-degree of an online vertex is the number of its future neighbors. To the best knowledge of the author, making use of the post-degree in online coloring lower bound construction seems to be new.

Technically, the online three-colorable graphs are constructed using bipartite graphs as building blocks. In particular, for the simulation with t<qt < q, given a construction of the qq-fold coloring, each online vertex in the qq-coloring model will be simulated by a collection of disjoint copies of certain bipartite graphs in the tt-fold coloring model. Each such bipartite graph has sufficiently many two-sided colors (which are produced via the independent set amplification), which allows to simulate the structure of the three-colorable graph in the qq-fold coloring model and force a set of qq new colors. The post-degree parameter in the qq-fold coloring gives us a handle to control both the number of vertices and the post-degree of the construction in the tt-fold coloring.

Randomized upper bound. We combine Vishwanathan’s anchor-sampling with an online form of Blum’s offline-monochromatic class compression and Wigderson’s degree control, in a new way.

Our randomized algorithm also uses the idea of anchor-sampling, but in expectation uses O(n)O(\sqrt{n}) anchors instead of O(n/log⁡n)O(\sqrt{n}/\log n). The main departure from Vishwanathan’s algorithm is that we only allow CBIP to use O(1)O(1) colors to color an anchor’s bipartite neighborhood, and send vertices exceeding this bound to recursive processing. It can be shown that such vertices necessarily form an offline-monochromatic class which allows for a similar effect of compression as in Blum’s offline coloring. For vertices with no anchored neighbor, we then process them by their degree, and similarly as in Wigderson simply color the low-degree vertices by (a randomized version of) FirstFit, and send the high-degree vertices to another recursive stream. For the low-degree vertices, we also only allow FirstFit to use O(1)O(1) colors, and for vertices that exceed this bound we again send them to another recursive stream. By properly designing the anchor-sampling, the degree threshold, and those disjoint palettes’ sizes, each of the three recursions is guaranteed to receive only a constant fraction of vertices, which provides an effect of compression that leads to O(n)O(\sqrt{n}) colors in expectation. As an example, the anchor-sampling and the degree control must work together to ensure that high degree vertices without anchored neighbor are not too many.

A lower bound for deterministic algorithms

We use tt-fold coloring to describe the recursive construction of the graph. In a tt-fold online coloring model, a vertex receives a set of tt distinct online colors, and adjacent vertices receive disjoint sets. We fix the target number KK of online colors throughout the construction. The auxiliary tt-fold model below lets us pass from one vertex in the KK-fold model to an ordinary coloring construction by a sequence of simulations, without changing this target.

We start with two simple combinatorial lemma that will be used a couple of times later.

Lemma 2.1. Let PP, QQ, XX be finite sets with ∣P∣|P|, ∣Q∣≥a|Q| \ge a, ∣X∣=t|X| = t, and X∩P=∅X \cap P = \varnothing. Put s=⌈t/2⌉s = \lceil t/2 \rceil. Then

max⁡{∣P∪Q∣,∣Q∪X∣}≥a+s.(1)\max\{|P \cup Q|, |Q \cup X|\} \ge a + s. \tag*{(1)}

Proof. If ∣P∪Q∣≥a+s|P \cup Q| \ge a + s, there is nothing to prove. Otherwise, ∣Q∖P∣≤a+s−1−∣P∣≤s−1|Q \setminus P| \le a + s - 1 - |P| \le s - 1. Since XX avoids PP, its intersection with QQ has size at most s−1s - 1. Consequently, ∣Q∪X∣≥a+t−s+1≥a+s|Q \cup X| \ge a + t - s + 1 \ge a + s.

Lemma 2.2. Let GG be a bipartite graph with sides AA, BB, where ∣A∣=a≥1|A| = a \ge1 and ∣B∣=b|B| = b. Suppose that every vertex of AA has degree at least the integer d≥1d \ge1. For every integer 1≤i≤a1 \le i \le a,

∣{u∈B:deg⁡(u)≥i}∣≥⌈ad−b(i−1)a−i+1⌉.(2)\left|\{u \in B : \deg(u) \ge i\}\right| \ge\left\lceil\frac{ad - b(i - 1)}{a - i + 1} \right\rceil. \tag*{(2)}

In particular, if a>ba > b, at least dd vertices of BB have degree at least two.

Proof. Write bi=∣{u∈B:deg⁡(u)≥i}∣b_i = |\{u \in B : \deg(u) \ge i\}| and let e=∣E(G)∣e = |E(G)|. We use double counting of the edges. Counting edges at AA gives e≥ade \ge ad. At BB, each of the bib_i vertices has degree at most aa, while all the others have degree at most i−1i - 1. Hence

ad≤e≤abi+(b−bi)(i−1)=b(i−1)+(a−i+1)bi.ad \le e \le ab_i + (b - b_i)(i - 1) = b(i - 1) + (a - i + 1)b_i.

Rearranging proves the claim. The in particular part can be directly verified with i=2i = 2.

Bipartite graphs forcing many two-sided colors

The goal of this part is to use the independent set amplification technique to give a construction of a bipartite graph forcing many two-sided colors in every tt-fold online coloring. These bipartite graphs will later be used as basic building blocks for simulation, or equivalently, in the recursive construction of three-colorable graphs.

For a colored vertex set SS, let col⁡(S)\operatorname{col}(S) be the union of its assigned online colors.

We first generalize the forest bipartite construction to the tt-fold coloring model, integrating the independent set amplification. For convenience, for bipartite graphs with a bipartition, we use side to denote one part of the bipartition.

Lemma 2.3. For integers t≥1t \ge1 and j≥0j \ge0, and every proper tt-fold coloring algorithm, there exists an adaptive bipartite graph construction using at most 2j+1−12^{j+1}-1 vertices such that one of its two sides, call it II, satisfying ∣col⁡(I)∣≥t+j⌈t/2⌉\lvert\operatorname{col}(I)\rvert\ge t+j\lceil t/2\rceil.

Proof. The construction will be inductive. At j=0j=0, present one vertex and take it as II. For j≥1j \ge1, present two disjoint copies of the level-(j−1)(j-1) construction, with designated sides I1,I2I_1,I_2, respectively. Write

P=col⁡(I1),Q=col⁡(I2),a=t+(j−1)s,s=⌈t/2⌉.P=\operatorname{col}(I_1),\qquad Q=\operatorname{col}(I_2),\qquad a=t+(j-1)s,\qquad s=\lceil t/2\rceil.

By induction, ∣P∣,∣Q∣≥a\lvert P\rvert,\lvert Q\rvert\ge a. Present a vertex xx adjacent to every vertex of I1I_1. Every tt-fold online coloring algorithm needs to use a set of tt colors on xx that is disjoint from col⁡(I1)\operatorname{col}(I_1).

Apply Lemma 2.1 to find a choice of the side call it II, which will be either the side contains I1∪I2I_1\cup I_2 or the side contains I2∪{x}I_2\cup\{x\}. Lemma 2.1 implies ∣col⁡(I)∣≥a+s\lvert\operatorname{col}(I)\rvert\ge a+s as desired. To verify the number of vertices, if mjm_j bounds the number of vertices, then m0=1m_0=1 and mj≤2mj−1+1m_j\le2m_{j-1}+1, giving mj≤2j+1−1m_j\le2^{j+1}-1.

Sine KK is our colors goal, a construction may stop immediately when KK distinct online colors have appeared. A color is two-sided in a bipartite graph with designated sides A,BA,B if it belongs to col⁡(A)∩col⁡(B)\operatorname{col}(A)\cap\operatorname{col}(B).

Lemma 2.4. Let K≥2K\ge2 and 1≤t≤q≤K1\le t\le q\le K. There exists a constant C>0C>0 such that for every tt-fold coloring algorithm, there is an adaptive bipartite graph construction with at most CK22Cq/tCK^2 2^{Cq/t} vertices which forces the algorithm to either use KK online colors globally or use at least qq two-sided colors.

Proof. Use Lemma 2.3 with j=⌈2q−t⌈t/2⌉⌉=O(q/t)j=\left\lceil\frac{2q-t}{\lceil t/2\rceil}\right\rceil=O(q/t). Present KK disjoint copies of that construction, call them G1,…,GKG_1,\ldots,G_K, each using 2O(q/t)2^{O(q/t)} vertices, where the two sides of GiG_i are denoted by (Ai,Bi)(A_i,B_i). Without loss of generality, assume the designated side is AiA_i, hence ∣col⁡(Ai)∣≥2q\lvert\operatorname{col}(A_i)\rvert\ge2q for every 1≤i≤K1\le i\le K. Throughout the proof suppose the global number of colors remains p≤K−1p\le K-1; otherwise we stop successfully.

Form a bipartite incidence graph. Its left side consists of the KK constructed graphs, and its right side consists of the pp online colors used globally. Join a graph to a color if that color occurs in its designated side. Every left degree is at least 2q2q. Apply Lemma 2.2 with a=K>p=ba=K>p=b, d=2qd=2q, and i=2i=2, gives at least 2q2q distinct colors each occurring in the designated sides of at least two different graphs.

We now apply a probabilistic argument to show that one can re-orient the two sides of each GiG_i so that the overall graph contains qq two-sided colors under the new orientation. For each AiA_i we flip an independent coin to decide it will be on the left or right side. Since each of the 2q2q colors appears in at least two distinct AiA_i’s from two disjoint bipartite graph GiG_i’s, each color has a probability of at least 1/21/2 to be two-sided. Therefore, in expectation there will be qq two-sided colors, and this implies the existence of such a desired orientation. □\square

Simulation of qq-fold coloring by tt-fold coloring

For a vertex vv in an online graph with arrival order π\pi, define its post-degree as the number of its future neighbors. We say a construction has size bound NN and post-degree bound DD if it uses at most NN vertices and every vertex has post-degree at most DD.

Lemma 2.5 (Simulation lemma). Let $1 \le t < q \le K$, D>0D > 0. There exists a constant C>0C > 0 such that, every three-colorable graph construction with size bound NN and post-degree bound DD forcing qq-fold coloring to use KK colors can be simulated by a three-colorable graph construction forcing tt-fold coloring to use KK colors, with size bound N′N' and post-degree bound D′D' satisfying

N′≤CKq2ND2Cq/t,D′≤CKq2D2Cq/t.(3)N' \le CK^2_q ND^{2Cq/t}, \qquad D' \le CK^2_q D^{2Cq/t}. \tag*{(3)}

Proof. Let GqG_q denote the given online qq-fold construction, our goal is to build an online graph GtG_t to simulate GqG_q. For each vertex v∈V(Gq)v \in V(G_q), let σ(v)⊆V(Gt)\sigma(v) \subseteq V(G_t) denote the collection of vertices in GtG_t that plays the role of simulating the single vertex v∈V(Gq)v \in V(G_q). Every σ(v)\sigma(v) consists of

R=KqD(4)R = KqD \tag*{(4)}

copies of the tt-fold bipartite construction from Lemma 2.4. By Lemma 2.4, each copy has at most B=CK2Cq/tB = CK^{2Cq/t} vertices. The factor DD reserves a separate copy for each possible future neighbor of a simulated vertex. This permits different copies to be oriented differently in an offline three-coloring, while also controlling the post-degree in the new construction, see Figure 3 and Figure 4 for illustrations.

The online simulation showing reserved bipartite copies in $\sigma(a)$, $\sigma(b)$, and $\sigma(c)$, with copies of $\sigma(v)$ connected by green and yellow sides

Figure 3. The online simulation. Each σ(w)\sigma(w) consists of R=KqDR = K_qD bipartite copies. The displayed array consists of qDqD reserved copies arranged in qq rows and DD columns: each column is reserved for simulating a future vertex in GqG_q (the notation (x)(x) in the figure indicates the corresponding column is reserved for a future vertex x∈V(Gq)x \in V(G_q) that is to be simulated in GtG_t), and every bipartite graph in row ii contains the two-sided color γw,i\gamma_{w,i}. The online simulation then has the flexibility of choosing either side.

The corresponding offline three-coloring of $G_q$ and $G_t$, with each bipartite block using offline colors 1 and 2

Figure 4. The corresponding offline three-coloring. Here each bipartite block corresponds to a column in Figure 3. The flexibility of choosing either side allows the graph GtG_t to be three-colorable as long as GqG_q is. If ϕ\phi is a three-coloring on GqG_q, then the bipartite graph σ(v)⊆Gt\sigma(v) \subseteq G_t will be colored by the two colors in {1,2,3}∖{ϕ(v)}\{1,2,3\}\setminus\{\phi(v)\}.

Throughout the simulation, we will maintain the following properties:

  • X: for every v∈Gqv \in G_q, col⁡(σ(v))⊇col⁡(v)\operatorname{col}(\sigma(v)) \supseteq\operatorname{col}(v);

  • Y: for each color i∈col⁡(v)i \in\operatorname{col}(v), there are DD copies in σ(v)\sigma(v) each of which contains the color ii as a two-sided color. Furthermore, these DD copies for distinct ii are disjoint, see Figure 3.

To simulate a general online vertex v∈V(Gq)v \in V(G_q), we construct σ(v)\sigma(v) as described before and will describe the online edge connection below. If KK colors appear globally in GtG_t, stop. Hence, we assume the number of colors used globally is at most K−1K - 1.

Online edge connection. Since the simulation can be done inductively, we assume properties hold for pre-neighbors of vv. Let w∈V(Gq)w \in V(G_q) be such a neighbor. We look at σ(w)\sigma(w). By the degree constraint DD of graph GqG_q and the property Y, there are qq unused copies (correspond to a column in Figure 3) in σ(w)\sigma(w) each contains a two-sided color ii for i∈col⁡(w)i \in\operatorname{col}(w). In each copy, we can choose a vertex of color ii from either side to connect to all vertices of σ(v)\sigma(v). This will make these copies become used and will not be used later. This finishes the online edge connection.

Properties X and Y for σ(v)\sigma(v). The online edge connection clearly simulates the coloring constraints of vv on σ(v)\sigma(v). Hence, σ(v)\sigma(v) uses at least qq colors that are disjoint from all col⁡(w)\operatorname{col}(w) for ww as pre-neighbor of vv.

Apply Lemma 2.4, we get that each copy in σ(v)\sigma(v) contains qq two-sided colors. Apply Lemma 2.2 similarly as in the proof for Lemma 2.4 with parameters

a=R,b=p,d=q,i=qD,a = R, \qquad b = p, \qquad d = q, \qquad i = qD,

we get that at least qq colors each occurs in at least qDqD copies in σ(v)\sigma(v). By renaming if necessary, we identify these qq colors as the set col⁡(v)\operatorname{col}(v). Then, property Y can be realized greedily: for color i∈col⁡(v)i \in\operatorname{col}(v), successively choose DD copies from its qDqD copies, disjoint from all previous choices.

Offline three-colorability of GtG_t. Fix a proper three-coloring ϕ:V(Gq)→{1,2,3}\phi: V(G_q) \to\{1,2,3\}. We color GtG_t so that every bipartite copy in σ(v)\sigma(v) uses only the two colors different from ϕ(w)\phi(w); see Figure 4. Process the collections σ(w)\sigma(w) in reverse order of the corresponding vertices of GqG_q. Consider a bipartite copy in σ(w)\sigma(w). If this copy was used for connections to a later collection σ(v)\sigma(v), give its selected side color ϕ(v)\phi(v) and its other side the unique color in {1,2,3}∖{ϕ(w),ϕ(v)}\{1,2,3\} \setminus\{\phi(w),\phi(v)\}. This is well-defined because wv∈E(Gq)wv \in E(G_q) implies ϕ(w)≠ϕ(v)\phi(w) \ne\phi(v), and each copy is used for connections to at most one later collection. If the copy has no such connection, color its two sides arbitrarily with the two colors different from ϕ(w)\phi(w). Clearly, this coloring is a legal three-coloring on GtG_t.

Size and post-degree. N′N' is clear: N′≤N⋅R⋅BN' \le N \cdot R \cdot B. For D′D', our construction makes sure that each vertex in GtG_t is connected to at most one σ(v)\sigma(v), besides, it may be connected to at most B−1B - 1 vertices in its bipartite copy. Hence, the post-degree D′D' is at most R⋅B+BR \cdot B + B. By choosing the constant C>0C > 0 suitably, both claimed upper bounds hold.

Finishing the proof

Proof of Theorem 1.1. Fix a sufficiently large integer KK. We first construct a three-colorable graph that forces KK colors in the ordinary online coloring model, while bounding its number of vertices.

Set

ℓ=log⁡K,β=⌈ℓ⌉,h=⌈log⁡βK⌉,th=K, ti=βi(0≤i≤h−1).\ell= \log K, \qquad\beta= \lceil\ell\rceil, \qquad h = \lceil\log_{\beta} K \rceil, \qquad t_h = K,\ t_i = \beta^i \quad(0 \le i \le h - 1).

These are integers satisfying

t0=1,th=K,ti<ti+1,ti+1ti≤β(0≤i<h).t_0 = 1, \qquad t_h = K, \qquad t_i < t_{i+1}, \qquad\frac{t_{i+1}}{t_i} \le\beta\quad(0 \le i < h).

Furthermore,

h≤ℓlog⁡ℓ+1=O(ℓlog⁡ℓ).h \le\frac{\ell}{\log\ell} + 1 = O\left(\frac{\ell}{\log\ell}\right).

In the KK-fold coloring model, one vertex forces KK colors. This construction has size bound Nh=1N_h = 1 and post-degree bound Dh=1D_h = 1, where the latter is an upper bound on its actual post-degree zero.

Apply Lemma 2.5 successively with

q=ti+1,t=ti,i=h−1,h−2,…,0.q = t_{i+1}, \qquad t = t_i, \qquad i = h - 1, h - 2, \ldots, 0.

The target number of colors remains the same integer KK throughout these applications. Let Ni,DiN_i, D_i denote the size and post-degree bounds of the resulting tit_i-fold construction. Every resulting construction is three-colorable and forces KK colors.

Choose an absolute constant C0≥1C_0 \ge1 sufficiently large and put

F=C0K32C0β.F = C_0 K^3 2^{C_0\beta}.

Since q≤Kq \le K and q/t≤βq/t \le\beta in every application, Lemma 2.5 gives

Di≤FDi+1,Ni≤FNi+1Di+1.(5)D_i \le F D_{i+1}, \qquad N_i \le F N_{i+1}D_{i+1}. \tag*{(5)}

By induction with the base case Dh=1D_h = 1 and Nh=1N_h = 1, we obtain that for s=h−is = h - i,

Di≤Fs,Ni≤Fs(s+1)/2.(6)D_i \le F^s, \qquad N_i \le F^{s(s+1)/2}. \tag*{(6)}

Because β=⌈ℓ⌉\beta= \lceil\ell\rceil, we have log⁡F=log⁡C0+3ℓ+C0β=O(ℓ)\log F = \log C_0 + 3\ell+ C_0\beta= O(\ell). Consequently,

log⁡N0≤h(h+1)2log⁡F=O(ℓ3(log⁡ℓ)2).\log N_0 \le\frac{h(h+1)}{2}\log F = O\left(\frac{\ell^3}{(\log\ell)^2}\right).

Since t0=1t_0 = 1, this is an ordinary online coloring construction. Thus there is an absolute constant A≥1A \ge1 such that, for every sufficiently large KK, it forces KK colors using at most

N0≤2A(log⁡K)3/(log⁡log⁡K)2.(7)N_0 \le2^{A(\log K)^3/(\log\log K)^2}. \tag*{(7)}

vertices.

We now express the bound in terms of the number of vertices. Let

x=log⁡n,s=x1/3(log⁡x)2/3,x = \log n,\qquad s = x^{1/3}(\log x)^{2/3},

and choose an absolute constant c>0c > 0 sufficiently small that 128Ac3≤1128Ac^3 \le1. Set K=⌈2cs⌉K = \lceil2^{cs}\rceil and ℓ=log⁡K\ell= \log K. For all sufficiently large nn,

cs≤ℓ≤cs+1≤2cs,log⁡ℓ≥14log⁡x.cs \le\ell\le cs + 1 \le2cs,\qquad\log\ell\ge\frac{1}{4}\log x.

Applying (7), we obtain

log⁡N0≤Aℓ3(log⁡ℓ)2≤A(2cs)3(14log⁡x)2=128Ac3x≤x.\log N_0 \le A\frac{\ell^3}{(\log\ell)^2} \le A\frac{(2cs)^3}{(\frac{1}{4}\log x)^2} = 128Ac^3x \le x.

Therefore N0≤nN_0 \le n, while the construction forces at least K≥2c(log⁡n)1/3(log⁡log⁡n)2/3K \ge2^{c(\log n)^{1/3}(\log\log n)^{2/3}} colors.

A randomized upper bound

By Remark 1.3, we assume that nn, the number of vertices of an online graph GG, is known.

An attempted algorithm and an overview of the design

Consider the algorithm described in Figure 5. One can see that it is a similar but slightly different version of Vishwanathan’s randomized algorithm discussed in Figure 2.

An attempted algorithm on n vertices

Figure 5. An attempted algorithm on nn vertices, with D=knD = k\sqrt{n}. The obstacle is that child-mono may contain too many vertices.

The idea is the following:

  • sample roughly n\sqrt{n} anchors by independently sampling each vertex to be an anchor with probability roughly 1/n1/\sqrt{n};

  • for anchor’s neighborhood, color it using CBIP but with only qq colors budget, and for vertices exceeding that budget, send them to a recursive processing that we call child-mono;

  • for vertices without any anchor: if it has degree at most DD, we color it by FirstFit using at most D+1D+1 colors, and for high-degree vertices, we send them again to a recursive processing that we call child-highdeg. Setting D=k⋅nD=k\cdot\sqrt{n} would guarantee that high-degree vertices are unlikely to have no sampled-anchor, hence the child-highdeg receives only about n/kn/k vertices in expectation.

Choosing q,k=Θ(1)q,k=\Theta(1) guarantees we use only O(n)O(\sqrt{n}) colors locally for both CBIP and FirstFit, and our goal would be achieved if we can show the children also use O(n)O(\sqrt{n}) colors: for this we would like to have a compression effect, that is, the size of each child is only a fraction of the whole instance. This can already be made true for child-highdeg, but there is no such obvious guarantee for child-mono.

Compressing the input to child-mono. We will show that although vertices go into child-mono might be many, nonetheless, they can be divided into groups, where each group is a subset of some offline-monochromatic class of GG, and the total number of such offline-monochromatic classes is only a fraction of nn. This allows a compression effect similar to Blum’s work as discussed before. We can think of each of those groups in child-mono as a single virtual vertex, in that sense we can show that the size of the virtual graph for child-mono is only a fraction of the size of GG. Each group (virtual vertex) can be colored using a single color in offline coloring, while in online coloring each group may still require many colors.

Vertex-label pair (v,ℓ)(v,\ell). Following the discussion, then, each vertex in child-mono should be viewed as a pair (v,ℓ)(v,\ell) where ℓ\ell denotes the group (i.e., a subset of some offline-monochromatic class) it belongs to. In other words, child-mono is a graph on virtual vertices ℓ\ell’s. Let us temporarily denote this online virtual graph by MM. Once we take this view of a vertex in child-mono, because our algorithm is intended to be recursive, we need to view every vertex going into each recursive instance this way, and every child will be viewed as a virtual graph on labels. Though, when we do recursive online coloring, we still need to color the real vertex vv, not label ℓ\ell.

For example, in the original instance GG, each vertex can be viewed as (v,v)(v,v) where vv is its own label. When a vertex vv goes into the child-mono MM of GG, it will appear as (v,ℓ)(v,\ell) where ℓ\ell denotes a label for some offline-monochromatic class of GG. If the vertex is further sent to the child-mono of MM, denoted by M^\hat{M}, then vv would appear as (v,ℓ^)(v,\hat{\ell}) where ℓ^\hat{\ell} denotes a label for some offline-monochromatic class of labels in the virtual graph MM, and hence M^\hat{M} would be a virtual graph on those ℓ^\hat{\ell}’s, etc.

How does this affect anchor-sampling? Once we take the virtual graph view, then in every recursive instance, it makes sense to do the anchor-sampling with respect to the virtual vertex (i.e., labels), and each label is only sampled once: this will guarantee we have the desired expected number of anchors.

How does this affect degree-control? Similarly, we test the degree of a vertex vv on the virtual graph instead of its real degree in GG. Since we do anchor-sampling with respect to the virtual vertex (i.e., label), the high-degree part does not change: it is still unlikely for a high virtual-degree vertex to have no anchored neighbor. However, for low-virtual-degree vertices, it is different.

Consider (v,ℓ)(v,\ell) to have virtual-degree at most DD in a virtual graph, that is, ℓ\ell is connected to at most DD distinct other labels, say ℓ(i)\ell^{(i)} for i=1,…,ti=1,\ldots,t where t≤Dt\leq D. Now, if we try FirstFit for vv, we would like vv to be colored by a color that is absent from ⋃i=1tcol⁡(ℓ(i))\bigcup_{i=1}^{t}\operatorname{col}(\ell^{(i)}). But since each ℓ(i)\ell^{(i)} is a group of vertices, which means each col⁡(ℓ(i))\operatorname{col}(\ell^{(i)}) is a set of colors instead of a single color, it is no longer necessarily true that vv can still be colored by at most D+1D+1 colors greedily. Therefore, in order to have certain control on the colors used on every label ℓ\ell, we choose a separate palette for each ℓ\ell (of constant size, say LL), and then we do the following: if (v,ℓ)(v,\ell) can be colored via FirstFit using the palette for ℓ\ell, we color it, otherwise we sent it to another recursive stream that we call child-lowdeg. Now, in order to make sure child-lowdeg is small, we choose the size-LL palette for each ℓ\ell randomly and independently from a large shared palette of size K≈DLK \approx DL. Since (v,ℓ)(v,\ell) has virtual degree at most DD, we can then show that with high probability (v,ℓ)(v,\ell) can be colored using the palette of ℓ\ell, in other words, the virtual graph of child-lowdeg would be small, as desired.

Virtual graphs and coloring rules

We now write HH for the current virtual graph and MM for an upper bound on its number of labels. The input consists of pairs (v,ℓ)(v,\ell). Let VℓV_\ell be the group of actual vertices carrying label ℓ\ell. We require each VℓV_\ell to be independent and the final virtual graph to be three-colorable. At the root, every vertex has its own label.

The vertices of HH are the labels received by the instance. Two labels are adjacent when an edge between their actual vertices has been revealed. The virtual graph records all received pairs and revealed edges, even when a vertex is colored by another palette or forwarded to a child. Thus HH only grows, and later arrivals may add edges between existing labels. All degrees below are degrees in HH. Labels are ordered by their first appearance.

Maintain offline-monochromatic classes by identifying the common neighbors of every edge of HH and taking the transitive closure. These classes only merge. The validity of these certificates is proved in Lemma 3.1.

Color sets and FirstFit. As in the lower-bound section, col⁡(S)\operatorname{col}(S) denotes the colors assigned to vertices in SS. For an ordered shared palette PP, write

col⁡P(ℓ)=col⁡(Vℓ)∩P.\operatorname{col}_{P}(\ell)=\operatorname{col}(V_\ell)\cap P.

Each group has a fixed color-table Tℓ⊆PT_\ell\subseteq P of size LL. FirstFit chooses the least color in

Tℓ∖⋃h∈NH(ℓ)col⁡P(h).(8)T_\ell\setminus\bigcup_{h\in N_H(\ell)}\operatorname{col}_{P}(h). \tag*{(8)}

It fails if this set is empty. Only this rule uses colors from PP, so

col⁡P(ℓ)⊆Tℓ,∣col⁡P(ℓ)∣≤L.(9)\operatorname{col}_{P}(\ell)\subseteq T_\ell,\qquad\lvert\operatorname{col}_{P}(\ell)\rvert\leq L. \tag*{(9)}

CBIP. A sampled label hh is an anchor, with its own palette of qq colors. Use local color names 1,…,q1,\ldots,q in each anchor palette; the same name in different palettes represents different actual colors. Let col⁡h(ℓ)\operatorname{col}_{h}(\ell) record the local colors accepted at ℓ\ell from hh’s palette.

For a request at ℓ∈NH(h)\ell\in N_H(h), consider its component in

Jh=H[NH(h)],J_h=H[N_H(h)],

and let YY be the side opposite ℓ\ell. The CBIP trial color is

c=min⁡(N>0∖⋃u∈Ycol⁡h(u)).(10)c=\min\left(\mathbb{N}_{>0}\setminus\bigcup_{u\in Y}\operatorname{col}_{h}(u)\right). \tag*{(10)}

Accept it if c≤qc\leq q and record it in col⁡h(ℓ)\operatorname{col}_{h}(\ell). This is the usual CBIP rule with retained color sets [11, 1, 10]. All accepted colors are retained throughout the run; a failed trial changes no color set.

The shared palette, the anchor palettes, and the palettes of different recursive instances and runs are mutually disjoint.

The full algorithm

Fix

k=216,L=8,q=2⌈log⁡k⌉+4=36.(11)k = 2^{16}, \qquad L = 8, \qquad q = 2\lceil\log k\rceil+ 4 = 36. \tag*{(11)}

For a label budget M≥1M \ge1, set

D=k⌈M⌉,K=4DL.(12)D = k\left\lceil\sqrt{M}\right\rceil, \qquad K = 4DL. \tag*{(12)}

All logarithms are to base 2.

Let Bt(M)B_t(M) be one run with at most MM distinct labels and remaining recursion depth tt. At t=0t = 0, give each group one private color. For t≥1t \ge1, create the shared palette PP of KK colors, start with empty virtual graph and color sets, and create three child streams: child-mono, child-highdeg, and child-lowdeg.

At the first appearance of ℓ\ell, independently sample it as an anchor with probability 1/⌈M⌉1/\left\lceil\sqrt{M}\right\rceil and, if sampled, reserve its qq anchor colors. Independently sample

Tℓ uniformly from (PL).T_{\ell}\text{ uniformly from }\binom{P}{L}.

All choices are independent across labels and runs. Later requests with the same label reuse its choices.

For forwarding to child-mono, each maintained class may have a class label. Create one only when needed and none exists. On a class merger, retain the earliest existing class label for future forwarding. Previously forwarded vertices keep their child labels.

Processing (v,ℓ)(v,\ell) in Bt(M)B_t(M). If t=0t = 0, give vv the private color of ℓ\ell and stop. Otherwise update HH, its classes, and inherited class labels. If ℓ\ell is new, perform its anchor and color-table sampling. Apply the following rules in order:

  1. Try CBIP. If ℓ\ell has a sampled neighbor, choose the earliest one hh and compute its CBIP trial color. On success, color vv from hh’s palette and record the color. On failure, forward vv to child-mono under its class label, creating that label if necessary.

  1. Degree check. If there is no sampled neighbor and deg⁡H(ℓ)>D\deg_H(\ell) > D, forward (v,ℓ)(v,\ell) to child-highdeg.

  1. Try FirstFit with TℓT_{\ell}. Otherwise, deg⁡H(ℓ)≤D\deg_H(\ell) \le D. If (8) supplies a color, assign it to vv and record it in col⁡P(ℓ)\operatorname{col}_P(\ell). If not, forward (v,ℓ)(v,\ell) to child-lowdeg.

Stop after the applicable rule. Every forwarded vertex is colored recursively before the next actual vertex arrives.

Each child receives the induced stream of actual vertices forwarded to it, with their specified labels. It uses the procedure At−1A_{t-1} below, with fresh independent randomness. The parent never uses the child’s output in its decisions.

Unknown child sizes. The procedure AtA_t starts with Bt(1)B_t(1). It tracks the cumulative number of distinct labels received. Before a request makes this count exceed the current budget MM, double MM and start a fresh Bt(M)B_t(M). The new run has empty state, new palettes and choices, and fresh child streams. It considers only vertices arriving during that run and edges between them. Earlier vertices retain their colors. Each run receives at most its budget’s number of labels; disjoint palettes handle edges across runs. Empty streams are not initialized.

Root. Set T=⌈log⁡(n+1)⌉T = \lceil\log(n+1)\rceil and submit the ii-th vertex as (vi,i)(v_i,i) to BT(n)B_T(n).

Fix an ordered input to one Bt(M)B_t(M) run independently of its random choices. Write mmono,mhighdeg,mlowdegm_{\mathrm{mono}},m_{\mathrm{highdeg}},m_{\mathrm{lowdeg}} for the numbers of distinct labels received by its children. We proceed to bound these.

Offline-monochromatic classes and child-mono

In this subsection we use properties of CBIP and the three-colorability of the overall graph to control the size of child-mono.

Lemma 3.1. Let GG be three-colorable and v∈V(G)v \in V(G). Each side of every connected component of G[NG(v)]G[N_G(v)] is an offline-monochromatic class.

Proof. Consider a length-two path x,u,yx,u,y in G[NG(v)]G[N_G(v)]. The vertices x,yx,y are common neighbors of the edge vuvu, so they receive the same color in every proper three-coloring, i.e., they belong to an offline-monochromatic class. Since any two vertices on the same side of a connected bipartite component are joined by an even path, the claim follows.

Lemma 3.2 (CBIP growth). On a bipartite graph, if CBIP uses color a≥2a \ge2 on a connected component, then each side of that component has at least 2⌊a/2⌋−12^{\lfloor a/2\rfloor-1} vertices.

Proof. We induct on aa. For a=2,3a=2,3, the component contains an edge. For a≥4a \ge4, put j=a−2j=a-2. At the occurrence of aa, the opposite side contains an occurrence of j+1j+1 at some vertex xx and an occurrence of jj at some vertex yy. When j+1j+1 was accepted at xx, there was an occurrence of jj at a vertex zz opposite xx. Thus y,zy,z lie on opposite sides of the current component.

At the later of these two specified occurrences of jj, the components of y,zy,z were distinct: otherwise the earlier occurrence would have forbidden the later one. Each component then had at least 2⌊j/2⌋−12^{\lfloor j/2\rfloor-1} vertices on each side by induction. Their later merger gives at least 2⋅2⌊j/2⌋−1=2⌊a/2⌋−12 \cdot2^{\lfloor j/2\rfloor-1}=2^{\lfloor a/2\rfloor-1} vertices on each side.

These two lemmas implies the following.

Corollary 3.3 (CBIP failure). For the fixed parameter qq, if in our algorithm CBIP needs to use color c>qc>q on a vertex vv, then the maintained offline-monochromatic class where vv belongs to contains at least kk vertices.

Proof. By Lemma 3.1 and Lemma 3.2, since c≥q+1=2⌈log⁡k⌉+5c \ge q+1=2\lceil\log k\rceil+5, the side containing vv has at least 2⌊c/2⌋−1≥2⌈log⁡k⌉+1≥k2^{\lfloor c/2\rfloor-1} \ge2^{\lceil\log k\rceil+1} \ge k vertices, and they all lie in one maintained offline-monochromatic class.

These statements apply directly to HH, whose vertices are labels. In particular, every class label created for child-mono represents a subset of a parent offline-monochromatic class containing at least kk labels.

Lemma 3.4. mmono≤M/km_{\mathrm{mono}} \le M/k, and its virtual graph is three-colorable.

Proof. By Corollary 3.3, at each class-label creation, choose kk parent labels in its class. The chosen sets are disjoint: a later class containing any previously chosen label inherits a class label and cannot cause another creation. Since the parent has at most MM labels, there are at most M/kM/k creations.

The three-colorability of virtual graph follows from the fact that each label denotes a subset of some offline-monochromatic class, and by definition each such class receives the same color in every fixed three-coloring, that is, the virtual vertex can be colored using the color for that class.

The high-degree and low-degree children

Lemma 3.5. Emhighdeg≤M/kE m_{\mathrm{highdeg}} \le M/k.

Proof. For a label ℓ\ell that ever has degree greater than DD, let SS be its neighbor set at the first such request. The input fixes SS, and ∣S∣>D|S| > D. If ℓ\ell ever enters child-highdeg, none of SS can be sampled, because its neighbor sets only grow. Therefore

P(ℓ enters child-highdeg)≤(1−1⌈M⌉)∣S∣≤e−∣S∣/M<e−k≤1k.\mathbb{P}(\ell\text{ enters child-highdeg}) \le\left(1-\frac{1}{\lceil\sqrt{M}\rceil}\right)^{|S|} \le e^{-|S|/\sqrt{M}} < e^{-k} \le\frac{1}{k}.

Summing over at most MM labels proves the claim.

Lemma 3.6. Emlowdeg≤M/kE m_{\mathrm{lowdeg}} \le M/k.

Proof. Condition on all anchor choices. The positions reaching FirstFit are now fixed independently of the color-tables: they have no sampled neighbor and degree at most DD.

For a label ℓ\ell reaching FirstFit, let SℓS_\ell be its neighbor set at the last such position. Then ∣Sℓ∣≤D|S_\ell| \le D, and SℓS_\ell contains the neighbor sets at all earlier FirstFit trials at ℓ\ell. Put

Uℓ=⋃h∈SℓTh,∣Uℓ∣≤DL.U_\ell=\bigcup_{h\in S_\ell}T_h,\qquad|U_\ell|\le DL.

Any failed trial at ℓ\ell implies Tℓ⊆UℓT_\ell\subseteq U_\ell, because col⁡P(h)⊆Th\operatorname{col}_{P}(h)\subseteq T_h.

Condition also on all color-tables other than TℓT_\ell. Since ℓ∉Sℓ\ell\notin S_\ell, the set UℓU_\ell is fixed and TℓT_\ell remains an independent uniform LL-subset of PP. Hence

P(Tℓ⊆Uℓ∣Uℓ)=(∣Uℓ∣L)(KL)≤(∣Uℓ∣K)L≤(DLK)L=4−L=1k.(13)\mathbb{P}(T_\ell\subseteq U_\ell\mid U_\ell) =\frac{\binom{|U_\ell|}{L}}{\binom{K}{L}} \le\left(\frac{|U_\ell|}{K}\right)^L \le\left(\frac{DL}{K}\right)^L =4^{-L} =\frac{1}{k}. \tag*{(13)}

This bounds the probability of any failure at ℓ\ell during the run. Sum over the labels and remove the conditioning.

Finishing the proof

We have shown

mmono≤M/k,Emhighdeg≤M/k,Emlowdeg≤M/k.(14)m_{\mathrm{mono}}\le M/k,\qquad\mathbb{E}m_{\mathrm{highdeg}}\le M/k,\qquad\mathbb{E}m_{\mathrm{lowdeg}}\le M/k. \tag*{(14)}

Now, we are ready to finish the proof.

Proof of Theorem 1.2. Properness. Child-mono preserves the recursive input condition by Lemma 3.4. The other children retain parent labels, so their virtual graphs are subgraphs of the parent’s virtual graph. Restricting to one budget run also preserves the condition.

An accepted CBIP color avoids the accepted colors on the opposite side of its current component. Every earlier actual neighbor colored from that anchor’s palette lies on this side. An accepted FirstFit color avoids the shared-palette colors of every neighboring group. At depth zero, the groups are independent and receive private colors. All other palettes are disjoint. Induction on the remaining depth therefore proves properness.

Local cost and child budgets. Set A=8kL+qA=8kL+q. The shared palette has

K=4kL⌈M⌉≤8kLMK=4kL\lceil\sqrt{M}\rceil\le8kL\sqrt{M}

colors, and the expected number of anchors is at most M/⌈M⌉≤MM/\lceil\sqrt{M}\rceil\le\sqrt{M}. Thus the expected local color cost is at most AMA\sqrt{M}. For a fixed child stream with m≥1m \ge1 labels, its budgets are 1,2,…,2s1,2,\ldots,2^s, where 2s<2m2^s < 2m. The geometric sums give

∑j=0s2j<5m,∑j=0s2j<4m.\sum_{j=0}^{s}\sqrt{2^j}<5\sqrt{m},\qquad\sum_{j=0}^{s}2^j<4m.

Consequently, a bound atM+dtMa_t\sqrt{M}+d_tM for Bt(M)B_t(M) on every fixed input gives a bound

5atm+4dtm(15)5a_t\sqrt{m}+4d_tm \tag*{(15)}

for AtA_t. An empty stream contributes zero.

The recurrence. We prove

E[colors used by Bt(M)]≤atM+dtM,\mathbb{E}[\text{colors used by }B_t(M)]\le a_t\sqrt{M}+d_tM,

where

a0=0,d0=1,a_0=0,\qquad d_0=1,
at=A+15kat−1,dt=12kdt−1.(16)a_t=A+\frac{15}{\sqrt{k}}a_{t-1},\qquad d_t=\frac{12}{k}d_{t-1}. \tag*{(16)}

The base case uses at most MM private colors.

For the induction step, condition on the parent’s random choices. Its three child streams are then fixed independently of their fresh random choices, since the parent never uses their output. Apply (15) and average over the parent choices. With I={mono,highdeg,lowdeg}\mathcal{I}=\{\text{mono},\text{highdeg},\text{lowdeg}\}, we get

E[colors used by Bt(M)]≤AM+5at−1∑i∈IEmi+4dt−1∑i∈IEmi≤AM+15at−1M/k+12dt−1M/k=atM+dtM.\begin{aligned} \mathbb{E}[\text{colors used by }B_t(M)]\le A\sqrt{M}+5a_{t-1}\sum_{i\in\mathcal{I}}\mathbb{E}\sqrt{m_i}+4d_{t-1}\sum_{i\in\mathcal{I}}\mathbb{E}m_i \\ &\le A\sqrt{M}+15a_{t-1}\sqrt{M/k}+12d_{t-1}M/k \\ &=a_t\sqrt{M}+d_tM. \end{aligned}

Here (14) and concavity give Emi≤Emi≤M/k\mathbb{E}\sqrt{m_i}\le\sqrt{\mathbb{E}m_i}\le\sqrt{M/k}. Since 15/k=15/256<1/215/\sqrt{k}=15/256<1/2 and 12/k<1/212/k<1/2,

at=A∑j=0t−1(15/k)j≤2A,dt=(12/k)t≤2−t.a_t=A\sum_{j=0}^{t-1}(15/\sqrt{k})^j\le2A,\qquad d_t=(12/k)^t\le2^{-t}.

At the root,

ECA(G,π)≤2An+2−Tn<2An+1=O(n).\mathbb{E}C_A(G,\pi)\le2A\sqrt{n}+2^{-T}n<2A\sqrt{n}+1=O(\sqrt{n}).

Each forwarding decreases the remaining depth, so a vertex visits at most T+1T+1 instances. Every budget is less than 2n2n. Maintaining the virtual graphs, classes, components, and color sets, and sampling the anchors and color-tables, takes expected polynomial time. This proves the theorem.

Declaration of AI Usage

The results and analysis are developed using ChatGPT Astra and the author’s previous preliminary studies. The author substantially simplified and reorganized the presentation that the AI tool gives. These includes but not limited to: simplify the proof for the lower bound and the randomized algorithm, write overviews and discuss the underlying ideas and connections to previous studies, sketch illustrations and flowchart that help present the ideas more clearly, etc. The author has verified the proofs and take full responsibility for the main contents (Theorem 1.1 and Theorem 1.2) of this article. The content in the appendix has only be loosely checked and is subject to future update.

A lower bound against randomized algorithms

An oblivious adversary fixes the ordered input independently of the algorithm’s random choices. We construct such an input distribution. All its graphs are three-colorable, including outcomes on which the simulation fails. Designated sets and bipartitions are part of the construction, not additional information supplied to the algorithm. All logarithms are to base 2, except for ln⁡\ln.

Theorem A.1. There is an absolute constant c>0c > 0 such that, for every sufficiently large nn and every randomized online coloring algorithm AA, some fixed ordered three-colorable graph satisfies

∣V(G)∣=n,ECA⁡A(G,π)≥2c(log⁡n)1/3(log⁡log⁡n)2/3.|V(G)| = n,\qquad\operatorname{ECA}_{A}(G,\pi) \ge2^{c(\log n)^{1/3}(\log\log n)^{2/3}}.

The expectation is over the algorithm’s random choices. The statement holds also when nn is supplied to the algorithm.

The constructions below replace the color-dependent choices in § 2 by input randomness. They always run to completion. Reaching KK colors is an event used in the analysis, not a reason to stop or change the input.

Oblivious bipartite constructions

Lemma A.2. For integers t≥1t \ge1 and j≥0j \ge0, there is a distribution on ordered bipartite graphs with a fixed number mj≤2⋅32jm_j \le2 \cdot32^j of vertices and a designated independent set II such that every deterministic tt-fold algorithm satisfies

P(∣col⁡(I)∣≥t+j⌈t2⌉)≥12.\mathbb{P}\left(|\operatorname{col}(I)| \ge t + j\left\lceil\frac{t}{2}\right\rceil\right) \ge\frac{1}{2}.

A bipartition placing II on one side is determined by the input randomness. The guarantee holds after any earlier history, also when all new vertices are joined to a common fixed earlier set UU.

Proof. At j=0j = 0, present one vertex and designate it. For j≥1j \ge1, present two independent level-(j−1)(j - 1) constructions, with designated sets I1,I2I_1, I_2, and then a vertex xx adjacent to every vertex of I1I_1. An independent fair coin designates either I1∪I2I_1 \cup I_2 or I2∪{x}I_2 \cup\{x\}. This coin affects no edge already presented and can remain hidden until these vertices have been colored.

Repeat this procedure sixteen times on disjoint vertices, and designate the union of their chosen sets. Put s=⌈t/2⌉s = \left\lceil t/2\right\rceil and a=t+(j−1)sa = t + (j - 1)s. Conditional on any history before a repetition, the two child designated sets both have at least aa colors with probability at least 1/41/4. This follows by applying the induction hypothesis first to the first child and then to the second child after the first has been revealed.

On that event, set

P=col⁡(I1),Q=col⁡(I2),X=col⁡({x}).P = \operatorname{col}(I_1),\qquad Q = \operatorname{col}(I_2),\qquad X = \operatorname{col}(\{x\}).

We have ∣X∣=t|X| = t and X∩P=∅X \cap P = \varnothing. Lemma 2.1 shows that one candidate designated set has at least a+sa + s colors. The hidden coin selects such a set with probability at least 1/21/2. Each repetition therefore succeeds with conditional probability at least 1/81/8, and

P(all sixteen repetitions fail)≤(7/8)16<12.\mathbb{P}(\text{all sixteen repetitions fail}) \le(7/8)^{16} < \frac{1}{2}.

Both choices lie on one side of suitable bipartitions. For the first choice, put I1,I2I_1, I_2 on the same side and xx on the other side. For the second, put I2,xI_2, x on the same side, opposite I1I_1. Orient the sixteen disjoint repetitions with their designated sets on the same side. These choices depend only on input coins. Finally,

m0=1,mj=16(2mj−1+1)≤2⋅32j.m_0 = 1,\qquad m_j = 16(2m_{j-1} + 1) \le2 \cdot32^j.

Additional adjacency to UU only forbids colors, so the same argument applies. All coins can be sampled before the input starts.

Lemma A.3. Let K≥2K \ge2 and $1 \le t \le q \le K$. There is an oblivious distribution on ordered bipartite graphs, with a designated bipartition and a fixed number

B≤CK2Cq/tB \le CK 2^{Cq/t}

of vertices, such that every deterministic tt-fold algorithm, after any earlier history, has probability at least 1/91/9 of either using KK colors globally or producing qq two-sided colors in this graph. All its vertices may additionally be joined to a common fixed earlier set UU.

Proof. Present 4K4K independent copies of Lemma A.2, with

j=⌈8q−t⌈t/2⌉⌉=O(q/t).j = \left\lceil\frac{8q-t}{\lceil t/2\rceil} \right\rceil= O(q/t).

Each designated set has at least 8q8q colors with conditional probability at least 1/21/2. For analysis, count a copy if this occurs or the global target KK has been reached by its completion. The expected number of uncounted copies is at most 2K2K. Markov’s inequality gives probability at least 1/31/3 that at least KK copies are counted.

Suppose this event occurs and the target has not been reached. Let p≤K−1p \le K-1 be the global number of colors. The incidence graph between any KK counted copies and these pp colors has left degree at least 8q8q. Lemma 2.2, with a=K>p=ba=K>p=b and d=8qd=8q, gives 8q8q colors each appearing in the designated sets of at least two copies.

Independently flip the structural bipartition of each of the 4K4K copies by a fair coin. These flips affect no edge within this construction, so they remain independent of its coloring. Each repeated color has probability at least 1/21/2 of occurring on both sides of the resulting bipartition. Fix 8q8q such colors for analysis, and let XX count those that become two-sided. Conditional on the history before the flips,

EX≥4q,0≤X≤8q.\mathop{\mathrm{E}}X \ge4q,\qquad0 \le X \le8q.

Since EX≤q+8qP(X≥q)\mathop{\mathrm{E}}X \le q+8q\mathop{\mathrm{P}}(X\ge q), we have P(X≥q)≥3/8≥1/3\mathop{\mathrm{P}}(X\ge q) \ge3/8 \ge1/3. The desired event thus has probability at least 1/91/9. The selected copies and colors are used only for analysis; they determine no edge. Finally,

B=4Kmj≤CK2Cq/t.B = 4Km_j \le CK 2^{Cq/t}.

The assertion with extra adjacency to UU follows from the preceding lemma.

An oblivious simulation lemma

Lemma A.4. Suppose a distribution on ordered three-colorable graphs has positive integer size and post-degree bounds N,DN,D and forces every deterministic qq-fold algorithm to use KK colors with probability at least ρ\rho. For $1 \le t < q \le Kand$0<ε<1and \$0 < \varepsilon< 1, there is an oblivious distribution forcing every deterministic tt-fold algorithm to use KK colors with probability at least ρ−ε\rho-\varepsilon. Every graph in its support is three-colorable, and its bounds satisfy

N′≤FND,D′≤FD,F=CK2ln⁡(2NKDε)2Cq/t.(17)N' \le FND,\qquad D' \le FD,\qquad F=CK^2\ln\left(\frac{2NKD}{\varepsilon}\right)2^{Cq/t}. \tag*{(17)}

Proof. Pad the given distribution to length NN with isolated vertices. For each simulated vertex vv, let σ(v)\sigma(v) consist of

R=⌈144KDln⁡(2NKDε)⌉(18)R=\left\lceil144KD\ln\left(\frac{2NKD}{\varepsilon}\right)\right\rceil \tag*{(18)}

independent copies of Lemma A.3, each of the same fixed size BB.

Independently assign every copy in σ(w)\sigma(w) a uniform index from [D][D], for its possible future neighbor. When vv arrives and is the aa-th future neighbor of ww, select the first designated side of every copy in σ(w)\sigma(w) having index aa. Let UvU_v be the union of these sides over all earlier neighbors ww of vv. Join every vertex of σ(v)\sigma(v) to all of UvU_v. Each copy serves at most one future simulated vertex. All edges depend only on the simulated graph and independent input coins, not on online colors. The indices assigned within σ(v)\sigma(v) affect no edge until a later simulated vertex arrives. For analysis, reveal them only after σ(v)\sigma(v) has been colored.

Three-colorability. Fix a proper three-coloring ϕ\phi of the simulated graph. Color every copy in σ(w)\sigma(w) with the two colors other than ϕ(w)\phi(w). If it is used for a later neighbor vv, orient it so its selected side has color ϕ(v)\phi(v). There is at most one such requirement per copy, and ϕ(v)≠ϕ(w)\phi(v) \ne\phi(w). Orient unused copies arbitrarily. Then UvU_v is monochromatic with color ϕ(v)\phi(v), whereas σ(v)\sigma(v) uses the other two colors. This gives a proper three-coloring on every outcome of the input coins.

Repeated colors. Fix a deterministic algorithm for the actual tt-fold input. For copy aa in σ(v)\sigma(v), let YaY_a indicate that it has qq two-sided colors or that the global target has been reached by its completion. After every preceding history,

P(Ya=1∣Fa−1)≥19.\mathbb{P}(Y_a=1 \mid\mathcal{F}_{a-1}) \ge\frac{1}{9}.

Thus

E(2−Ya∣Fa−1)≤1718,E2−∑a=1RYa≤e−R/18.\mathbb{E}(2^{-Y_a} \mid\mathcal{F}_{a-1}) \le\frac{17}{18}, \qquad\mathbb{E}2^{-\sum_{a=1}^{R}Y_a} \le e^{-R/18}.

Markov’s inequality yields

P(∑a=1RYa<R/18)≤2R/18e−R/18≤e−R/72.(19)\mathbb{P}\left(\sum_{a=1}^{R}Y_a < R/18\right) \le2^{R/18}e^{-R/18} \le e^{-R/72}. \tag*{(19)}

Suppose fewer than KK global colors have appeared and G≥R/18G \ge R/18 copies have qq two-sided colors. Choose qq such colors from each good copy for analysis. At least qq distinct colors each occur in at least G/(2K)G/(2K) of these selections. Otherwise their total number of occurrences would be at most

(q−1)G+(K−q)G2K<qG.(q-1)G + (K-q)\frac{G}{2K} < qG.

contrary to the qGqG selected occurrences. Choose qq such colors as the provisional simulated set col⁡(v)\operatorname{col}(v), before revealing the indices in σ(v)\sigma(v). Each is two-sided in at least R/(36K)R/(36K) copies.

Coverage of future-neighbor positions. Conditional on the colored copies and this provisional set, their indices are still independent and uniform on [D][D]. For one provisional color and one index, the probability that no copy carrying that color on both sides receives the index is at most

(1−1/D)R/(36K)≤e−R/(36KD).(1-1/D)^{R/(36K)} \le e^{-R/(36KD)}.

Except with probability qDe−R/(36KD)qDe^{-R/(36KD)}, every provisional color therefore occurs on selected sides at every index.

Let EvE_v mean that the actual target has not been reached by completion of σ(v)\sigma(v) and either the required number of good copies or this coverage property fails. Then, conditional on the preceding history,

P(Ev)≤e−R/72+qDe−R/(36KD)≤εN.\mathbb{P}(E_v) \le e^{-R/72}+qDe^{-R/(36KD)} \le\frac{\varepsilon}{N}.

Indeed, put Z=2NKD/εZ=2NKD/\varepsilon. By (A.2), the terms are at most Z−2Z^{-2} and KDZ−4KDZ^{-4}, respectively, each at most ε/(2N)\varepsilon/(2N). Consequently,

P(⋃vEv)≤ε.(20)\mathbb{P}\left(\bigcup_v E_v\right) \le\varepsilon. \tag*{(20)}

The simulated coloring. Define an online qq-fold algorithm on the simulated input. It runs the fixed actual algorithm with the independent input coins above. Until the actual target is reached or the first event Ev\mathcal{E}_v occurs, it supplies the provisional set col⁡(v)\operatorname{col}(v). At either event, it switches permanently to fresh qq-sets, disjoint from all previously supplied colors and from each other.

This algorithm is proper on every outcome. Before the switch, for any earlier neighbor ww of vv, coverage puts every color of col⁡(w)\operatorname{col}(w) in UvU_v. Every actual vertex of σ(v)\sigma(v) avoids these colors, as does col⁡(v)\operatorname{col}(v). Fresh sets preserve properness after the switch.

The simulated algorithm uses only the revealed simulated prefix, and its coins are independent of that input. Fixing them gives a deterministic qq-fold algorithm, so the hypothesis implies simulated success with probability at least ρ\rho. If the actual target is never reached and no Ev\mathcal{E}_v occurs, no switch happens and every simulated color is an actual color. Equation (A.4) therefore gives actual success probability at least ρ−ε\rho-\varepsilon. The provisional sets and the switch affect only the analysis, never the actual input distribution.

Size and post-degree. We have N′=NRBN' = NRB. A vertex has at most B−1B-1 future neighbors inside its own copy. Its external future neighbors belong to the unique later collection served by that copy. Hence

D′≤B−1+RB<(R+1)B.D' \le B-1+RB < (R+1)B.

Together with B≤CK2Cq/tB \le CK2^{Cq/t} and (A.2), this proves (A.1).

Finishing the proof

Proof of Theorem A.1. Fix a sufficiently large target KK, and set

ℓ=log⁡K,β=⌈ℓ⌉,h=⌊log⁡βK⌋,th=K,ti=βi(0≤i<h).\ell=\log K,\qquad\beta=\lceil\ell\rceil,\qquad h=\left\lfloor\log_{\beta}K\right\rfloor,\qquad t_h=K,\qquad t_i=\beta^i\quad(0\le i<h).

Then h=O(ℓ/log⁡ℓ)h=O(\ell/\log\ell) and ti+1/ti≤βt_{i+1}/t_i\le\beta. A singleton in the KK-fold model reaches the target with probability one, with Nh=Dh=1N_h=D_h=1. Apply Lemma A.4 successively with

q=ti+1,t=ti,ε=14h,i=h−1,…,0.q=t_{i+1},\qquad t=t_i,\qquad\varepsilon=\frac{1}{4h},\qquad i=h-1,\ldots,0.

The final ordinary-coloring distribution forces KK colors against every deterministic algorithm with probability at least 3/43/4.

We check that the additional logarithmic factor does not change the bound. As long as N,D≤2ℓ4N,D\le2^{\ell^4},

CK2ln⁡(8hNKD)2Cβ≤KC0CK^2\ln(8hNKD)2^{C\beta}\le K^{C_0}

for an absolute constant C0C_0 and sufficiently large KK. Put F=KC0F=K^{C_0}. The size and post-degree recurrences give, as in (6),

Di≤Fh−i,Ni≤F(h−i)(h−i+1)/2.D_i\le F^{h-i},\qquad N_i\le F^{(h-i)(h-i+1)/2}.

These bounds stay inside the assumed envelope, since

log⁡Ni,log⁡Di≤O(ℓh2)=O(ℓ3(log⁡ℓ)2)<ℓ4.\log N_i,\log D_i\le O(\ell h^2)=O\left(\frac{\ell^3}{(\log\ell)^2}\right)<\ell^4.

Induction therefore justifies the envelope and gives

N0≤2O((log⁡K)3/(log⁡log⁡K)2).N_0\le2^{O((\log K)^3/(\log\log K)^2)}.

For each fixed seed of a randomized algorithm, this same input distribution forces KK colors with probability at least 3/43/4. Averaging over its independent seed gives expected color count at least 3K/43K/4, averaged over the input distribution. Some fixed ordered graph in the support consequently has expected color count at least 3K/43K/4.

Choose

K=⌈22c(log⁡n)1/3(log⁡log⁡n)2/3⌉K=\left\lceil2^{2c(\log n)^{1/3}(\log\log n)^{2/3}}\right\rceil

for a sufficiently small absolute constant c>0c>0. The same inversion as in the deterministic proof gives N0≤nN_0\le n and, for sufficiently large nn,

3K4≥2c(log⁡n)1/3(log⁡log⁡n)2/3.\frac{3K}{4}\ge2^{c(\log n)^{1/3}(\log\log n)^{2/3}}.

Pad to exactly nn vertices with isolated vertices. All distributional guarantees hold for every deterministic algorithm, including one supplied with this value of nn.

A deterministic algorithm in the random order model

In the random order model, the graph is fixed and its vertices arrive in a uniformly random order. The algorithm sees only the edges to earlier vertices. We do not assume fixed vertex identifiers: arrival positions are the only names available to the algorithm.

Theorem B.1. There is a deterministic polynomial-time online coloring algorithm D\mathcal{D} that properly colors every ordered three-colorable graph and, on every fixed three-colorable graph GG with nn vertices, satisfies

EπCD(G,π)=O(n),\mathbb{E}_{\pi}\mathcal{C}_{\mathcal{D}}(G,\pi)=O(\sqrt{n}),

where π\pi is uniform. The algorithm uses no external random bits and need not know nn.

We first implement a variant of the randomized algorithm with O(log⁡2n)O(\log^2 n) fair bits. We then obtain those bits from already revealed edges, using few colors before starting that algorithm.

A finite random seed

The following variant keeps the same virtual graphs, color sets, and routing rules as § 3.3. It changes the anchor probabilities, the shared-palette size, and the distribution of the color-tables. Every color-table still has LL distinct colors.

Lemma B.2. For every integer N≥1N\ge1, there is a seeded online algorithm ANA_N using

R(N)=8(32+⌈log⁡(N+1)⌉)⌈log⁡(N+1)⌉R(N)=8\bigl(32+\lceil\log(N+1)\rceil\bigr)\lceil\log(N+1)\rceil

fair bits, such that every seed gives a proper coloring and every fixed ordered three-colorable input with at most NN vertices has expected color cost at most C0NC_0\sqrt{N}. Here C0C_0 is absolute, and the running time is polynomial in NN.

Proof. Keep k=216k=2^{16}, L=8L=8, and q=36q=36. For a run with label budget MM, use

r=2⌈log⁡M⌉,D=kr,K=210DL,r=2^{\lceil\log\sqrt{M}\rceil},\qquad D=kr,\qquad K=2^{10}DL,

sampling anchors with probability 1/r1/r. These quantities are powers of two. Use the root BT(N)B_T(N) with T=⌈log⁡(N+1)⌉T=\lceil\log(N+1)\rceil and the same child-budget procedure as in the main algorithm.

We describe sufficient local independence before generating it from the seed. Pairwise independent anchor indicators suffice. Indeed, for the fixed neighbor set SS at a label’s first request of degree greater than DD, let YY count sampled neighbors. Then

λ=EY=∣S∣/r>k,Var⁡(Y)≤λ.\lambda=\mathbb{E}Y=|S|/r>k,\qquad\operatorname{Var}(Y)\le\lambda.

The argument of Lemma 3.5 therefore gives

P(ℓ enters child-highdeg)≤P(Y=0)≤1/λ<1/k.\mathbb{P}(\ell\text{ enters child-highdeg})\le\mathbb{P}(Y=0)\le1/\lambda<1/k.

Identify the ordered shared palette with the field FK\mathbb{F}_K. Fix distinct elements η1,…,ηL\eta_1,\ldots,\eta_L. For each label ℓ\ell, obtain uniform field parameters aℓ,bℓa_\ell,b_\ell, put

aℓ′={aℓ,aℓ≠0,1,aℓ=0,Tℓ={aℓ′ηj+bℓ:1≤j≤L}.a'_\ell= \begin{cases} a_\ell, & a_\ell\ne0,\\ 1, & a_\ell= 0, \end{cases} \qquad T_\ell=\{a'_\ell\eta_j+b_\ell:1\le j\le L\}.

The table has LL distinct colors. Require six-wise independence of all parameter positions (ℓ,0)(\ell,0), (ℓ,1)(\ell,1) and independence from the anchor choices.

For any two prescribed values, the probability that the first two displayed table entries equal those values is at most 2/K22/K^2. Indeed, the pair determines aℓ′,bℓa'_\ell,b_\ell, and this parameter pair has at most two preimages among the K2K^2 equally likely choices of aℓ,bℓa_\ell,b_\ell.

Condition on the anchors and use the last eligible neighbor set SℓS_\ell from Lemma 3.6. A failed FirstFit trial implies that each of the first two table entries agrees with some entry at a label in SℓS_\ell. There are at most (DL)2(DL)^2 specifications of these agreements. A fixed specification involves at most three labels and six parameter positions. Their joint independence and the preceding bound give

Pr⁡(ℓ ever enters child-lowdeg)≤2(DL/K)2=2−19≤1/k.\Pr(\ell\text{ ever enters child-lowdeg})\le2(DL/K)^2=2^{-19}\le1/k.

This argument conditions only on the parameters occurring in a specified agreement, rather than on all other color-tables.

The child-mono bound from Corollary 3.3 and Lemma 3.4 is deterministic and unchanged. Here the proof of Lemma 3.2 applies also to retained color sets, repeated requests, and later edge additions: the occurrences in its argument are accepted requests, components only merge, and a retained color on the opposite side forbids a new occurrence. For a failed trial, apply that argument after hypothetically accepting its color; no earlier color set changes. The expected local cost is at most A∗MA_*\sqrt{M}, where

A∗=211kL+q.A_* = 2^{11}kL+q.

Thus the recurrence (16), with A∗A_* in place of AA, again gives a root cost at most (2A∗+1)N(2A_*+1)\sqrt{N}.

It remains to generate the choices with a short seed. Put w=32+⌈log⁡(N+1)⌉w=32+\lceil\log(N+1)\rceil and fix a binary representation of F2w\mathbb{F}_{2^w}. All descendant budgets are below 2N2N. Consequently all local first-appearance positions and their two parameter positions have injective field encodings, and

K<2302N<232(N+1)≤2w.K<2^{30}\sqrt{2N}<2^{32}(N+1)\le2^w.

At each recursion distance d=0,…,T−1d=0,\ldots,T-1, choose independently a uniform polynomial of degree at most one and an independent uniform polynomial of degree at most five over F2w\mathbb{F}_{2^w}. Use the first polynomial at a label’s local first-appearance position; the label is an anchor when the first log⁡r\log r binary coordinates of its value are zero. Use the second polynomial at the two parameter positions of each label; project its values onto their first log⁡K\log K coordinates and interpret these as elements of FK\mathbb{F}_K. Polynomial evaluations give the required pairwise and six-wise independence, respectively, by the Vandermonde formula.

The polynomial pair at distance dd is shared by all runs at that distance. To justify this reuse, condition on the polynomial choices at smaller distances. All streams, labels, and budget boundaries at distance dd are then fixed: parents never use their children’s output. The current polynomial pair is independent of that conditioning, so every run has the local marginal distributions just analyzed. Sharing may correlate different runs, but their costs are added in expectation. After exposing this distance’s pair, the same argument applies to the next distance. Thus the main inductive color-count proof remains valid.

There are eight field coefficients at each of TT distances, requiring exactly 8wT8wT fair bits. All further operations are deterministic. The fields and their representations can be constructed in polynomial time in NN; even enumerating binary polynomials and testing irreducibility suffices, since 2w=O(N+1)2^w=O(N+1). Properness uses only the retained color sets and disjoint palettes, so it holds for every seed.

Obtaining bits from revealed edges

Fix a desired seed length R≥1R \ge1. For a completed block (v1,…,va)(v_1,\ldots,v_a), put p=⌊a/3⌋p=\lfloor a/3\rfloor. Pair its first 2p2p positions consecutively, and let

W=(v2p+1,…,va)W=(v_{2p+1},\ldots,v_a)

be the ordered witness list. The signature of a paired vertex xx is

sW(x)=(1xv2p+1∈E,…,1xva∈E).s_W(x)=(\mathbf{1}_{xv_{2p+1}\in E},\ldots,\mathbf{1}_{xv_a\in E}).

A pair is usable if its signatures differ. A usable ordered pair (x,y)(x,y) supplies the bit 1sW(x)>lexsW(y)\mathbf{1}_{s_W(x)>_{\mathrm{lex}}s_W(y)}. The block test succeeds when there are at least RR usable pairs, and outputs the first RR bits in pair-position order. The test is performed only after the block is complete, when all these edges have been revealed.

Lemma B.3. For a fixed block of positions in a uniform random presentation, condition on the unordered two-element set in each pair, the ordered witness list, and the entire order outside the block. Usability is then fixed, and the usable pairs supply independent unbiased bits.

Proof. The remaining possibilities are the independent orientations of the paired sets, all equally likely. Reversing a usable pair reverses its bit and changes neither its usability nor the indices selected by the test.

We next bound the cost of waiting for a successful block. Write ν(F)\nu(F) for the maximum matching size of a graph FF. Ordinary FirstFit uses at most 2ν(F)+12\nu(F)+1 colors in every order. Indeed, for each i≤⌊c/2⌋i \le\lfloor c/2\rfloor, a vertex of FirstFit color 2i2i has an earlier neighbor of color 2i−12i-1. If cc colors are used, these edges form a matching because their pairs of endpoint colors are disjoint.

Lemma B.4. Let FF be a fixed three-colorable graph on mm vertices, with ν=ν(F)≥1024\nu=\nu(F)\ge1024. In a uniform random order, test a fixed interval of a≥m/4a\ge m/4 positions. If QQ is its number of usable pairs, then

P(Q<αν)≤e−βν,α=2−22,β=2−23.\mathbb{P}(Q<\alpha\nu)\le e^{-\beta\nu},\qquad\alpha=2^{-22},\qquad\beta=2^{-23}.

Proof. First find ρ=⌊ν/8⌋\rho=\lfloor\nu/8\rfloor disjoint edges xiwix_iw_i and a set ZZ, disjoint from their endpoints, satisfying

∣Z∣≥m/5,E({w1,…,wρ},Z)=∅.|Z|\ge m/5,\qquad E(\{w_1,\ldots,w_\rho\},Z)=\varnothing.

For this purpose only, fix an offline independent color class II of size at least m/3m/3. Let hh be the maximum matching size between II and its complement.

If h≥ν/8h\ge\nu/8, choose ρ\rho crossing edges with wi∈Iw_i\in I and set Z=I∖{w1,…,wρ}Z=I\setminus\{w_1,\ldots,w_\rho\}. Then ∣Z∣≥m/3−m/16>m/5|Z|\ge m/3-m/16>m/5. Otherwise, let UU be the endpoints of a maximum crossing matching. These endpoints cover every crossing edge, and ∣U∣<ν/4|U|<\nu/4. Deleting UU from a maximum matching of FF leaves more than 3ν/43\nu/4 edges, all outside I∪UI\cup U. Choose ρ\rho of them and set Z=I∖UZ=I\setminus U. Now

∣Z∣≥m/3−ν/4≥5m/24>m/5,|Z|\ge m/3-\nu/4\ge5m/24>m/5,

and the required nonadjacencies hold.

View the random order as a uniform placement into mm positions. The tested block has at least m/12m/12 witness positions and at least m/6−2m/6-2 paired positions. Expose the placement in s=⌊ρ/6⌋s=\lfloor\rho/6\rfloor trials. At each trial choose an edge whose endpoints remain unexposed. Reveal the positions of wi,xiw_i,x_i, and if xix_i occupies a paired position whose partner is unexposed, reveal that partner.

A trial is good if wiw_i occupies a witness position, xix_i occupies such an intact paired position, and its partner lies in ZZ. Each trial exposes at most three vertices and touches at most three of the chosen disjoint edges, so an untouched edge is always available. Before a trial fewer than ρ/2≤m/32\rho/2 \le m/32 vertices have been exposed. Conditional on the past, the remaining placement is uniform. The three successive favorable probabilities are at least

m/12−m/32m≥132,m/6−2−2(m/32+1)m≥116,m/5−m/32−2m≥18.\frac{m/12-m/32}{m} \ge\frac{1}{32}, \qquad\frac{m/6-2-2(m/32+1)}{m} \ge\frac{1}{16}, \qquad\frac{m/5-m/32-2}{m} \ge\frac{1}{8}.

Here m≥2ν≥2048m \ge2\nu\ge2048. Thus every trial is conditionally good with probability at least p0=2−12p_0=2^{-12}.

A good trial gives a usable pair, because xix_i is adjacent to the witness wiw_i, whereas its partner in ZZ is not. Different good trials give different pairs. If SS counts good trials, then Q≥SQ \ge S. Successive conditioning gives, for λ>0\lambda> 0,

Ee−λS≤(1−p0+p0e−λ)s.\mathbb{E}e^{-\lambda S} \le(1-p_0+p_0e^{-\lambda})^s.

Taking λ=ln⁡2\lambda=\ln2 and applying exponential Markov yields P(S<p0s/2)≤e−p0s/8\mathbb{P}(S < p_0s/2) \le e^{-p_0s/8}. Finally,

ρ≥ν/16,s≥ρ/12≥ν/192,p0s≥ν/220.\rho\ge\nu/16, \qquad s \ge\rho/12 \ge\nu/192, \qquad p_0s \ge\nu/2^{20}.

The stated α,β\alpha,\beta therefore suffice.

The deterministic algorithm

Lemma B.5. Suppose a seeded online algorithm properly colors every ordered three-colorable graph of at most NN vertices for every seed in {0,1}R\{0,1\}^R, and its expected cost under a uniform seed is at most FF. There is a deterministic online algorithm with expected cost

F+O(R+log⁡log⁡(N+2))F+O(R+\log\log(N+2))

in random order. It needs no fixed vertex identifiers.

Proof. Run ordinary FirstFit while dividing arriving positions into blocks of lengths 1,2,4,…1,2,4,\ldots. Test each completed block. At the first success, use its RR bits to run the seeded algorithm on the remaining induced graph, ignoring the prefix and using a disjoint palette. If no block succeeds, FirstFit colors the entire input. Every order receives a proper coloring.

Let the actual graph have n≤Nn \le N vertices. For analysis define the test outcomes of all completed blocks, even if the algorithm has already switched. Let JJ be the first successful block, or the final occupied block if none succeeds. Let PjP_j be the prefix through block jj, including a final incomplete block, and put

X=ν(G[PJ]),h=1+⌈log⁡(n+1)⌉.X=\nu(G[P_J]), \qquad h=1+\lceil\log(n+1)\rceil.

For j≥1j \ge1, the preceding block is complete and occupies more than ∣Pj∣/4|P_j|/4 positions. Conditional on the unordered set PjP_j, its order is uniform. For x≥x0=max⁡{1024,R/α}x \ge x_0=\max\{1024,R/\alpha\}, Lemma B.4 therefore gives

P(Qj−1<R, ν(G[Pj])≥x)≤e−βx.\mathbb{P}(Q_{j-1}<R,\ \nu(G[P_j])\ge x)\le e^{-\beta x}.

The event J=j≥1J=j\ge1 requires Qj−1<RQ_{j-1}<R. For J=0J=0, the prefix has one vertex and X=0X=0. A union bound gives

P(X≥x)≤min⁡{1,he−βx}(x≥x0).\mathbb{P}(X\ge x)\le\min\{1,he^{-\beta x}\}\qquad(x\ge x_0).

Summing the tail yields

EX≤x0+ln⁡h+1β+1=O(R+log⁡log⁡(n+2)).\mathbb{E}X\le x_0+\frac{\ln h+1}{\beta}+1=O(R+\log\log(n+2)).

The FirstFit prefix uses at most 2X+12X+1 colors.

To analyze the suffix, suppose block jj is the first successful one. Condition on the entire order outside this block, its unordered paired sets, and its ordered witness list. All earlier test outcomes and all current usability decisions are fixed by this information. The event of first switching here is therefore invariant under independent reversals of the current pairs. By Lemma B.3, the extracted seed remains uniform under this conditioning, while the ordered suffix is fixed. The suffix algorithm ignores the prefix, so its conditional expected cost is at most FF. Adding the prefix bound proves the claim.

Proof of Theorem B.1. For a known budget NN, apply Lemma B.5 to AN\mathcal{A}_N from Lemma B.2. Since R(N)=O(log⁡2(N+1))R(N) = O(\log^2(N + 1)), the resulting expected cost is

C0N+O(log⁡2(N+1)+log⁡log⁡(N+2))=O(N).C_0\sqrt{N} + O(\log^2(N + 1) + \log\log(N + 2)) = O(\sqrt{N}).

For unknown nn, divide arriving positions into fixed outer epochs of capacities 1,2,4,…1, 2, 4, \ldots. Run the budget-NN algorithm in an epoch of capacity NN, with fresh state and a palette disjoint from other epochs. Conditional on the vertex set of an epoch, its internal order is uniform, including the incomplete final epoch. Thus its expected cost is O(N)O(\sqrt{N}). The largest capacity used is at most nn, and the geometric sum of their square roots is O(n)O(\sqrt{n}).

All tests compare adjacency vectors of already revealed vertices; no fixed vertex identifiers or external random bits are used. The tests and the seeded algorithm run in polynomial time. Disjoint palettes at switches and epoch boundaries ensure properness for every order.

References

  1. [1]Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, and Lucia Keller. Online coloring of bipartite graphs with and without advice. Algorithmica, 70(1):92–111, 2014.
  2. [3]Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470–516, 1994.DOI
  3. [4]Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu. Lower bounds for on-line graph colorings. In Algorithms and Computation (ISAAC 2014), volume 8889 of Lecture Notes in Computer Science, pages 507–515, 2014.DOI
  4. [5]András Gyárfás and Jenő Lehel. On-line and first fit colorings of graphs. Journal of Graph Theory, 12(2):217–227, 1988.DOI
  5. [6]H. A. Kierstead. Coloring graphs on-line. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms: The State of the Art, volume 1442 of Lecture Notes in Computer Science, pages 281–305. Springer, 1998.DOI
  6. [7]H. A. Kierstead. On-line coloring k-colorable graphs. Israel Journal of Mathematics, 105:93–104, 1998.
  7. [8]Ken-ichi Kawarabayashi, Mikkel Thorup, and Hirotaka Yoneda. Better coloring of 3-colorable graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 331–339. ACM, 2024.arxiv.org/abs/2406.00357
  8. [9]Ken-ichi Kawarabayashi, Hirotaka Yoneda, and Masataka Yoneda. Online graph coloring for k-colorable graphs. https://arxiv.org/abs/2511.16100, 2025. Revised April 2026.
  9. [10]Yaqiao Li, Vishnu V. Narayan, and Denis Pankratov. Online coloring and a new type of adversary for online graph problems. Algorithmica, 84(5):1232–1251, 2022.
  10. [11]László Lovász, Michael Saks, and William T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, 75(1–3):319–325, 1989.
  11. [12]Sundar Vishwanathan. Randomized online graph coloring. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, pages 464–469, 1990.
  12. [13]Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729–735, 1983.DOI

Paper details

vlnc:W_9h6m7wv9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT Astra

View statement
Looking for related papers…
Contents