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 to . For the upper bound of randomized algorithms, we give a randomized algorithm that achieves improving Vishwanathan's . Technically, for the lower bound construction, we introduce the language of -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 , an order , and an algorithm , write for the number of colors used. In 1990, Vishwanathan [12] proved that every deterministic online algorithm requires colors to color three-colorable graphs on vertices, and gave a randomized algorithm that uses 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 such that, for every sufficiently large and every deterministic online coloring algorithm , some ordered three-colorable graph on vertices satisfies
Theorem 1.2 (Randomized upper bound). There is a randomized online algorithm such that, for every fixed ordered three-colorable graph with at most vertices,
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 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 .
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.
As in Vishwanathan [12], the two bounds we obtained could be generalized to get new bounds for online coloring on -colorable graphs for . We did not try to do that.
Closely related work
Offline coloring three-colorable graphs: Wigderson and Blum. Wigderson’s -color algorithm [13] used two facts: the neighbourhood of a vertex in a three-colorable graph is bipartite, and a graph of maximum degree admits a greedy -coloring. Wigderson’s algorithm then proceeded by checking vertex degree: for degree at least , it two-colored its neighborhood of at least vertices and removed the neighborhood. There were at most such removals. The remaining graph had degree below and was colored greedily.
Blum [3] obtained 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 is an edge, then all vertices incident to both and 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 -vertex forest (hence, bipartite) construction forcing colors on every deterministic algorithm.
It is not hard to see that FirstFit can use up to colors on bipartite graphs of vertices, such as on crown graphs, see Y et al. [XYW+26]. However, a useful feature of FirstFit is that if it uses color on an online vertex , it is guaranteed that there are at least vertices arrived before that are all connected to and exhausted the colors .
Lovász, Saks, and Trotter [11] gave an online coloring algorithm, which became known as CBIP, using at most colors for bipartite graphs on 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 . 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 bound when at most 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 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 lower bound and an 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 with at least online colors. Construct a disjoint copy with such a set . Next construct a bipartite graph , joining all its vertices to . One of two parts of , say , has colors on an -vertex bipartite construction. Note that colors used on is necessarily disjoint from colors used on . A simple calculation shows that either the independent set or has at least colors. This amplification process can then be repeated within certain range of the related parameters, forcing at least colors. This technique is also used in our lower bound construction.

Figure 1. The independent set amplification in Vishwanathan’s lower-bound construction: either or forces new online colors if .
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 FirstFit colors. At the start it chose an index uniformly from . For each arriving online vertex the algorithm tried to color it using FirstFit with at most colors. In case when an online vertex needed to use color by FirstFit, the feature of FirstFit guaranteed a neighbor of in the color class . The vertex was then used as an anchor and was colored by CBIP in the bipartite neighborhood of , using at most colors. Each anchor used a separate palette of at most colors. Since the expected size of the vertices in was at most , the total colors was at most
Figure 2. Vishwanathan’s randomized algorithm.
Note that the expected number of anchors was . 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 colors for three-colorable graphs. For -colorable graphs with ,
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 -fold online coloring model: each vertex is assigned a set of distinct colors, and distinct vertices use disjoint color sets. The standard online coloring model corresponds to . Suppose our goal is to force colors, we can trivially force it using a single vertex in the -fold coloring model, and then our task is to ask whether it is possible to force colors in the standard 1-fold coloring and using how many vertices. This suggests interpolation and simulation: if one can force colors using -fold coloring and vertices, given , can you simulate it (i.e., also force colors) using -fold coloring and vertices for some as a function of , , , ? Clearly, such a simulation lemma can then be used to build a lower bound construction.
Hence, fixing , the goal is to upper bound as a function of , , , . 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 , given a construction of the -fold coloring, each online vertex in the -coloring model will be simulated by a collection of disjoint copies of certain bipartite graphs in the -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 -fold coloring model and force a set of new colors. The post-degree parameter in the -fold coloring gives us a handle to control both the number of vertices and the post-degree of the construction in the -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 anchors instead of . The main departure from Vishwanathan’s algorithm is that we only allow CBIP to use 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 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 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 -fold coloring to describe the recursive construction of the graph. In a -fold online coloring model, a vertex receives a set of distinct online colors, and adjacent vertices receive disjoint sets. We fix the target number of online colors throughout the construction. The auxiliary -fold model below lets us pass from one vertex in the -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 , , be finite sets with , , , and . Put . Then
Proof. If , there is nothing to prove. Otherwise, . Since avoids , its intersection with has size at most . Consequently, .
Lemma 2.2. Let be a bipartite graph with sides , , where and . Suppose that every vertex of has degree at least the integer . For every integer ,
In particular, if , at least vertices of have degree at least two.
Proof. Write and let . We use double counting of the edges. Counting edges at gives . At , each of the vertices has degree at most , while all the others have degree at most . Hence
Rearranging proves the claim. The in particular part can be directly verified with .
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 -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 , let be the union of its assigned online colors.
We first generalize the forest bipartite construction to the -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 and , and every proper -fold coloring algorithm, there exists an adaptive bipartite graph construction using at most vertices such that one of its two sides, call it , satisfying .
Proof. The construction will be inductive. At , present one vertex and take it as . For , present two disjoint copies of the level- construction, with designated sides , respectively. Write
By induction, . Present a vertex adjacent to every vertex of . Every -fold online coloring algorithm needs to use a set of colors on that is disjoint from .
Apply Lemma 2.1 to find a choice of the side call it , which will be either the side contains or the side contains . Lemma 2.1 implies as desired. To verify the number of vertices, if bounds the number of vertices, then and , giving .
Sine is our colors goal, a construction may stop immediately when distinct online colors have appeared. A color is two-sided in a bipartite graph with designated sides if it belongs to .
Lemma 2.4. Let and . There exists a constant such that for every -fold coloring algorithm, there is an adaptive bipartite graph construction with at most vertices which forces the algorithm to either use online colors globally or use at least two-sided colors.
Proof. Use Lemma 2.3 with . Present disjoint copies of that construction, call them , each using vertices, where the two sides of are denoted by . Without loss of generality, assume the designated side is , hence for every . Throughout the proof suppose the global number of colors remains ; otherwise we stop successfully.
Form a bipartite incidence graph. Its left side consists of the constructed graphs, and its right side consists of the online colors used globally. Join a graph to a color if that color occurs in its designated side. Every left degree is at least . Apply Lemma 2.2 with , , and , gives at least 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 so that the overall graph contains two-sided colors under the new orientation. For each we flip an independent coin to decide it will be on the left or right side. Since each of the colors appears in at least two distinct ’s from two disjoint bipartite graph ’s, each color has a probability of at least to be two-sided. Therefore, in expectation there will be two-sided colors, and this implies the existence of such a desired orientation.
Simulation of -fold coloring by -fold coloring
For a vertex in an online graph with arrival order , define its post-degree as the number of its future neighbors. We say a construction has size bound and post-degree bound if it uses at most vertices and every vertex has post-degree at most .
Lemma 2.5 (Simulation lemma). Let $1 \le t < q \le K$, . There exists a constant such that, every three-colorable graph construction with size bound and post-degree bound forcing -fold coloring to use colors can be simulated by a three-colorable graph construction forcing -fold coloring to use colors, with size bound and post-degree bound satisfying
Proof. Let denote the given online -fold construction, our goal is to build an online graph to simulate . For each vertex , let denote the collection of vertices in that plays the role of simulating the single vertex . Every consists of
copies of the -fold bipartite construction from Lemma 2.4. By Lemma 2.4, each copy has at most vertices. The factor 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.

Figure 3. The online simulation. Each consists of bipartite copies. The displayed array consists of reserved copies arranged in rows and columns: each column is reserved for simulating a future vertex in (the notation in the figure indicates the corresponding column is reserved for a future vertex that is to be simulated in ), and every bipartite graph in row contains the two-sided color . The online simulation then has the flexibility of choosing either side.

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 to be three-colorable as long as is. If is a three-coloring on , then the bipartite graph will be colored by the two colors in .
Throughout the simulation, we will maintain the following properties:
X: for every , ;
Y: for each color , there are copies in each of which contains the color as a two-sided color. Furthermore, these copies for distinct are disjoint, see Figure 3.
To simulate a general online vertex , we construct as described before and will describe the online edge connection below. If colors appear globally in , stop. Hence, we assume the number of colors used globally is at most .
Online edge connection. Since the simulation can be done inductively, we assume properties hold for pre-neighbors of . Let be such a neighbor. We look at . By the degree constraint of graph and the property Y, there are unused copies (correspond to a column in Figure 3) in each contains a two-sided color for . In each copy, we can choose a vertex of color from either side to connect to all vertices of . This will make these copies become used and will not be used later. This finishes the online edge connection.
Properties X and Y for . The online edge connection clearly simulates the coloring constraints of on . Hence, uses at least colors that are disjoint from all for as pre-neighbor of .
Apply Lemma 2.4, we get that each copy in contains two-sided colors. Apply Lemma 2.2 similarly as in the proof for Lemma 2.4 with parameters
we get that at least colors each occurs in at least copies in . By renaming if necessary, we identify these colors as the set . Then, property Y can be realized greedily: for color , successively choose copies from its copies, disjoint from all previous choices.
Offline three-colorability of . Fix a proper three-coloring . We color so that every bipartite copy in uses only the two colors different from ; see Figure 4. Process the collections in reverse order of the corresponding vertices of . Consider a bipartite copy in . If this copy was used for connections to a later collection , give its selected side color and its other side the unique color in . This is well-defined because implies , 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 . Clearly, this coloring is a legal three-coloring on .
Size and post-degree. is clear: . For , our construction makes sure that each vertex in is connected to at most one , besides, it may be connected to at most vertices in its bipartite copy. Hence, the post-degree is at most . By choosing the constant suitably, both claimed upper bounds hold.
Finishing the proof
Proof of Theorem 1.1. Fix a sufficiently large integer . We first construct a three-colorable graph that forces colors in the ordinary online coloring model, while bounding its number of vertices.
Set
These are integers satisfying
Furthermore,
In the -fold coloring model, one vertex forces colors. This construction has size bound and post-degree bound , where the latter is an upper bound on its actual post-degree zero.
Apply Lemma 2.5 successively with
The target number of colors remains the same integer throughout these applications. Let denote the size and post-degree bounds of the resulting -fold construction. Every resulting construction is three-colorable and forces colors.
Choose an absolute constant sufficiently large and put
Since and in every application, Lemma 2.5 gives
By induction with the base case and , we obtain that for ,
Because , we have . Consequently,
Since , this is an ordinary online coloring construction. Thus there is an absolute constant such that, for every sufficiently large , it forces colors using at most
vertices.
We now express the bound in terms of the number of vertices. Let
and choose an absolute constant sufficiently small that . Set and . For all sufficiently large ,
Applying (7), we obtain
Therefore , while the construction forces at least colors.
A randomized upper bound
By Remark 1.3, we assume that , the number of vertices of an online graph , 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.

Figure 5. An attempted algorithm on vertices, with . The obstacle is that child-mono may contain too many vertices.
The idea is the following:
sample roughly anchors by independently sampling each vertex to be an anchor with probability roughly ;
for anchor’s neighborhood, color it using CBIP but with only 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 , we color it by FirstFit using at most colors, and for high-degree vertices, we send them again to a recursive processing that we call child-highdeg. Setting would guarantee that high-degree vertices are unlikely to have no sampled-anchor, hence the child-highdeg receives only about vertices in expectation.
Choosing guarantees we use only colors locally for both CBIP and FirstFit, and our goal would be achieved if we can show the children also use 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 , and the total number of such offline-monochromatic classes is only a fraction of . 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 . 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 . Following the discussion, then, each vertex in child-mono should be viewed as a pair where 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 ’s. Let us temporarily denote this online virtual graph by . 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 , not label .
For example, in the original instance , each vertex can be viewed as where is its own label. When a vertex goes into the child-mono of , it will appear as where denotes a label for some offline-monochromatic class of . If the vertex is further sent to the child-mono of , denoted by , then would appear as where denotes a label for some offline-monochromatic class of labels in the virtual graph , and hence would be a virtual graph on those ’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 on the virtual graph instead of its real degree in . 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 to have virtual-degree at most in a virtual graph, that is, is connected to at most distinct other labels, say for where . Now, if we try FirstFit for , we would like to be colored by a color that is absent from . But since each is a group of vertices, which means each is a set of colors instead of a single color, it is no longer necessarily true that can still be colored by at most colors greedily. Therefore, in order to have certain control on the colors used on every label , we choose a separate palette for each (of constant size, say ), and then we do the following: if can be colored via FirstFit using the palette for , 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- palette for each randomly and independently from a large shared palette of size . Since has virtual degree at most , we can then show that with high probability can be colored using the palette of , in other words, the virtual graph of child-lowdeg would be small, as desired.
Virtual graphs and coloring rules
We now write for the current virtual graph and for an upper bound on its number of labels. The input consists of pairs . Let be the group of actual vertices carrying label . We require each to be independent and the final virtual graph to be three-colorable. At the root, every vertex has its own label.
The vertices of 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 only grows, and later arrivals may add edges between existing labels. All degrees below are degrees in . Labels are ordered by their first appearance.
Maintain offline-monochromatic classes by identifying the common neighbors of every edge of 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, denotes the colors assigned to vertices in . For an ordered shared palette , write
Each group has a fixed color-table of size . FirstFit chooses the least color in
It fails if this set is empty. Only this rule uses colors from , so
CBIP. A sampled label is an anchor, with its own palette of colors. Use local color names in each anchor palette; the same name in different palettes represents different actual colors. Let record the local colors accepted at from ’s palette.
For a request at , consider its component in
and let be the side opposite . The CBIP trial color is
Accept it if and record it in . 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
For a label budget , set
All logarithms are to base 2.
Let be one run with at most distinct labels and remaining recursion depth . At , give each group one private color. For , create the shared palette of 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 , independently sample it as an anchor with probability and, if sampled, reserve its anchor colors. Independently sample
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 in . If , give the private color of and stop. Otherwise update , its classes, and inherited class labels. If is new, perform its anchor and color-table sampling. Apply the following rules in order:
Try CBIP. If has a sampled neighbor, choose the earliest one and compute its CBIP trial color. On success, color from ’s palette and record the color. On failure, forward to child-mono under its class label, creating that label if necessary.
Degree check. If there is no sampled neighbor and , forward to child-highdeg.
Try FirstFit with . Otherwise, . If (8) supplies a color, assign it to and record it in . If not, forward 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 below, with fresh independent randomness. The parent never uses the child’s output in its decisions.
Unknown child sizes. The procedure starts with . It tracks the cumulative number of distinct labels received. Before a request makes this count exceed the current budget , double and start a fresh . 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 and submit the -th vertex as to .
Fix an ordered input to one run independently of its random choices. Write 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 be three-colorable and . Each side of every connected component of is an offline-monochromatic class.
Proof. Consider a length-two path in . The vertices are common neighbors of the edge , 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 on a connected component, then each side of that component has at least vertices.
Proof. We induct on . For , the component contains an edge. For , put . At the occurrence of , the opposite side contains an occurrence of at some vertex and an occurrence of at some vertex . When was accepted at , there was an occurrence of at a vertex opposite . Thus lie on opposite sides of the current component.
At the later of these two specified occurrences of , the components of were distinct: otherwise the earlier occurrence would have forbidden the later one. Each component then had at least vertices on each side by induction. Their later merger gives at least vertices on each side.
These two lemmas implies the following.
Corollary 3.3 (CBIP failure). For the fixed parameter , if in our algorithm CBIP needs to use color on a vertex , then the maintained offline-monochromatic class where belongs to contains at least vertices.
Proof. By Lemma 3.1 and Lemma 3.2, since , the side containing has at least vertices, and they all lie in one maintained offline-monochromatic class.
These statements apply directly to , 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 labels.
Lemma 3.4. , and its virtual graph is three-colorable.
Proof. By Corollary 3.3, at each class-label creation, choose 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 labels, there are at most 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. .
Proof. For a label that ever has degree greater than , let be its neighbor set at the first such request. The input fixes , and . If ever enters child-highdeg, none of can be sampled, because its neighbor sets only grow. Therefore
Summing over at most labels proves the claim.
Lemma 3.6. .
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 .
For a label reaching FirstFit, let be its neighbor set at the last such position. Then , and contains the neighbor sets at all earlier FirstFit trials at . Put
Any failed trial at implies , because .
Condition also on all color-tables other than . Since , the set is fixed and remains an independent uniform -subset of . Hence
This bounds the probability of any failure at during the run. Sum over the labels and remove the conditioning.
Finishing the proof
We have shown
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 . The shared palette has
colors, and the expected number of anchors is at most . Thus the expected local color cost is at most . For a fixed child stream with labels, its budgets are , where . The geometric sums give
Consequently, a bound for on every fixed input gives a bound
for . An empty stream contributes zero.
The recurrence. We prove
where
The base case uses at most 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 , we get
Here (14) and concavity give . Since and ,
At the root,
Each forwarding decreases the remaining depth, so a vertex visits at most instances. Every budget is less than . 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 .
Theorem A.1. There is an absolute constant such that, for every sufficiently large and every randomized online coloring algorithm , some fixed ordered three-colorable graph satisfies
The expectation is over the algorithm’s random choices. The statement holds also when is supplied to the algorithm.
The constructions below replace the color-dependent choices in § 2 by input randomness. They always run to completion. Reaching 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 and , there is a distribution on ordered bipartite graphs with a fixed number of vertices and a designated independent set such that every deterministic -fold algorithm satisfies
A bipartition placing 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 .
Proof. At , present one vertex and designate it. For , present two independent level- constructions, with designated sets , and then a vertex adjacent to every vertex of . An independent fair coin designates either or . 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 and . Conditional on any history before a repetition, the two child designated sets both have at least colors with probability at least . 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
We have and . Lemma 2.1 shows that one candidate designated set has at least colors. The hidden coin selects such a set with probability at least . Each repetition therefore succeeds with conditional probability at least , and
Both choices lie on one side of suitable bipartitions. For the first choice, put on the same side and on the other side. For the second, put on the same side, opposite . Orient the sixteen disjoint repetitions with their designated sets on the same side. These choices depend only on input coins. Finally,
Additional adjacency to only forbids colors, so the same argument applies. All coins can be sampled before the input starts.
Lemma A.3. Let 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
of vertices, such that every deterministic -fold algorithm, after any earlier history, has probability at least of either using colors globally or producing two-sided colors in this graph. All its vertices may additionally be joined to a common fixed earlier set .
Proof. Present independent copies of Lemma A.2, with
Each designated set has at least colors with conditional probability at least . For analysis, count a copy if this occurs or the global target has been reached by its completion. The expected number of uncounted copies is at most . Markov’s inequality gives probability at least that at least copies are counted.
Suppose this event occurs and the target has not been reached. Let be the global number of colors. The incidence graph between any counted copies and these colors has left degree at least . Lemma 2.2, with and , gives colors each appearing in the designated sets of at least two copies.
Independently flip the structural bipartition of each of the 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 of occurring on both sides of the resulting bipartition. Fix such colors for analysis, and let count those that become two-sided. Conditional on the history before the flips,
Since , we have . The desired event thus has probability at least . The selected copies and colors are used only for analysis; they determine no edge. Finally,
The assertion with extra adjacency to 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 and forces every deterministic -fold algorithm to use colors with probability at least . For $1 \le t < q \le K, there is an oblivious distribution forcing every deterministic -fold algorithm to use colors with probability at least . Every graph in its support is three-colorable, and its bounds satisfy
Proof. Pad the given distribution to length with isolated vertices. For each simulated vertex , let consist of
independent copies of Lemma A.3, each of the same fixed size .
Independently assign every copy in a uniform index from , for its possible future neighbor. When arrives and is the -th future neighbor of , select the first designated side of every copy in having index . Let be the union of these sides over all earlier neighbors of . Join every vertex of to all of . 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 affect no edge until a later simulated vertex arrives. For analysis, reveal them only after has been colored.
Three-colorability. Fix a proper three-coloring of the simulated graph. Color every copy in with the two colors other than . If it is used for a later neighbor , orient it so its selected side has color . There is at most one such requirement per copy, and . Orient unused copies arbitrarily. Then is monochromatic with color , whereas 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 -fold input. For copy in , let indicate that it has two-sided colors or that the global target has been reached by its completion. After every preceding history,
Thus
Markov’s inequality yields
Suppose fewer than global colors have appeared and copies have two-sided colors. Choose such colors from each good copy for analysis. At least distinct colors each occur in at least of these selections. Otherwise their total number of occurrences would be at most
contrary to the selected occurrences. Choose such colors as the provisional simulated set , before revealing the indices in . Each is two-sided in at least copies.
Coverage of future-neighbor positions. Conditional on the colored copies and this provisional set, their indices are still independent and uniform on . For one provisional color and one index, the probability that no copy carrying that color on both sides receives the index is at most
Except with probability , every provisional color therefore occurs on selected sides at every index.
Let mean that the actual target has not been reached by completion of and either the required number of good copies or this coverage property fails. Then, conditional on the preceding history,
Indeed, put . By (A.2), the terms are at most and , respectively, each at most . Consequently,
The simulated coloring. Define an online -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 occurs, it supplies the provisional set . At either event, it switches permanently to fresh -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 of , coverage puts every color of in . Every actual vertex of avoids these colors, as does . 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 -fold algorithm, so the hypothesis implies simulated success with probability at least . If the actual target is never reached and no occurs, no switch happens and every simulated color is an actual color. Equation (A.4) therefore gives actual success probability at least . The provisional sets and the switch affect only the analysis, never the actual input distribution.
Size and post-degree. We have . A vertex has at most future neighbors inside its own copy. Its external future neighbors belong to the unique later collection served by that copy. Hence
Together with and (A.2), this proves (A.1).
Finishing the proof
Proof of Theorem A.1. Fix a sufficiently large target , and set
Then and . A singleton in the -fold model reaches the target with probability one, with . Apply Lemma A.4 successively with
The final ordinary-coloring distribution forces colors against every deterministic algorithm with probability at least .
We check that the additional logarithmic factor does not change the bound. As long as ,
for an absolute constant and sufficiently large . Put . The size and post-degree recurrences give, as in (6),
These bounds stay inside the assumed envelope, since
Induction therefore justifies the envelope and gives
For each fixed seed of a randomized algorithm, this same input distribution forces colors with probability at least . Averaging over its independent seed gives expected color count at least , averaged over the input distribution. Some fixed ordered graph in the support consequently has expected color count at least .
Choose
for a sufficiently small absolute constant . The same inversion as in the deterministic proof gives and, for sufficiently large ,
Pad to exactly vertices with isolated vertices. All distributional guarantees hold for every deterministic algorithm, including one supplied with this value of .
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 that properly colors every ordered three-colorable graph and, on every fixed three-colorable graph with vertices, satisfies
where is uniform. The algorithm uses no external random bits and need not know .
We first implement a variant of the randomized algorithm with 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 distinct colors.
Lemma B.2. For every integer , there is a seeded online algorithm using
fair bits, such that every seed gives a proper coloring and every fixed ordered three-colorable input with at most vertices has expected color cost at most . Here is absolute, and the running time is polynomial in .
Proof. Keep , , and . For a run with label budget , use
sampling anchors with probability . These quantities are powers of two. Use the root with 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 at a label’s first request of degree greater than , let count sampled neighbors. Then
The argument of Lemma 3.5 therefore gives
Identify the ordered shared palette with the field . Fix distinct elements . For each label , obtain uniform field parameters , put
The table has distinct colors. Require six-wise independence of all parameter positions , 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 . Indeed, the pair determines , and this parameter pair has at most two preimages among the equally likely choices of .
Condition on the anchors and use the last eligible neighbor set 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 . There are at most specifications of these agreements. A fixed specification involves at most three labels and six parameter positions. Their joint independence and the preceding bound give
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 , where
Thus the recurrence (16), with in place of , again gives a root cost at most .
It remains to generate the choices with a short seed. Put and fix a binary representation of . All descendant budgets are below . Consequently all local first-appearance positions and their two parameter positions have injective field encodings, and
At each recursion distance , choose independently a uniform polynomial of degree at most one and an independent uniform polynomial of degree at most five over . Use the first polynomial at a label’s local first-appearance position; the label is an anchor when the first 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 coordinates and interpret these as elements of . Polynomial evaluations give the required pairwise and six-wise independence, respectively, by the Vandermonde formula.
The polynomial pair at distance 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 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 distances, requiring exactly fair bits. All further operations are deterministic. The fields and their representations can be constructed in polynomial time in ; even enumerating binary polynomials and testing irreducibility suffices, since . 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 . For a completed block , put . Pair its first positions consecutively, and let
be the ordered witness list. The signature of a paired vertex is
A pair is usable if its signatures differ. A usable ordered pair supplies the bit . The block test succeeds when there are at least usable pairs, and outputs the first 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 for the maximum matching size of a graph . Ordinary FirstFit uses at most colors in every order. Indeed, for each , a vertex of FirstFit color has an earlier neighbor of color . If colors are used, these edges form a matching because their pairs of endpoint colors are disjoint.
Lemma B.4. Let be a fixed three-colorable graph on vertices, with . In a uniform random order, test a fixed interval of positions. If is its number of usable pairs, then
Proof. First find disjoint edges and a set , disjoint from their endpoints, satisfying
For this purpose only, fix an offline independent color class of size at least . Let be the maximum matching size between and its complement.
If , choose crossing edges with and set . Then . Otherwise, let be the endpoints of a maximum crossing matching. These endpoints cover every crossing edge, and . Deleting from a maximum matching of leaves more than edges, all outside . Choose of them and set . Now
and the required nonadjacencies hold.
View the random order as a uniform placement into positions. The tested block has at least witness positions and at least paired positions. Expose the placement in trials. At each trial choose an edge whose endpoints remain unexposed. Reveal the positions of , and if occupies a paired position whose partner is unexposed, reveal that partner.
A trial is good if occupies a witness position, occupies such an intact paired position, and its partner lies in . 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 vertices have been exposed. Conditional on the past, the remaining placement is uniform. The three successive favorable probabilities are at least
Here . Thus every trial is conditionally good with probability at least .
A good trial gives a usable pair, because is adjacent to the witness , whereas its partner in is not. Different good trials give different pairs. If counts good trials, then . Successive conditioning gives, for ,
Taking and applying exponential Markov yields . Finally,
The stated therefore suffice.
The deterministic algorithm
Lemma B.5. Suppose a seeded online algorithm properly colors every ordered three-colorable graph of at most vertices for every seed in , and its expected cost under a uniform seed is at most . There is a deterministic online algorithm with expected cost
in random order. It needs no fixed vertex identifiers.
Proof. Run ordinary FirstFit while dividing arriving positions into blocks of lengths . Test each completed block. At the first success, use its 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 vertices. For analysis define the test outcomes of all completed blocks, even if the algorithm has already switched. Let be the first successful block, or the final occupied block if none succeeds. Let be the prefix through block , including a final incomplete block, and put
For , the preceding block is complete and occupies more than positions. Conditional on the unordered set , its order is uniform. For , Lemma B.4 therefore gives
The event requires . For , the prefix has one vertex and . A union bound gives
Summing the tail yields
The FirstFit prefix uses at most colors.
To analyze the suffix, suppose block 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 . Adding the prefix bound proves the claim.
Proof of Theorem B.1. For a known budget , apply Lemma B.5 to from Lemma B.2. Since , the resulting expected cost is
For unknown , divide arriving positions into fixed outer epochs of capacities . Run the budget- algorithm in an epoch of capacity , 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 . The largest capacity used is at most , and the geometric sum of their square roots is .
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]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.
- [3]Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470–516, 1994.DOI
- [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
- [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
- [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
- [7]H. A. Kierstead. On-line coloring k-colorable graphs. Israel Journal of Mathematics, 105:93–104, 1998.
- [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
- [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.
- [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.
- [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.
- [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.
- [13]Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729–735, 1983.DOI