WorksComputer Science
Online Graph Coloring with Random Arrivals
Abstract
We study online graph coloring in the random-arrival model, where the vertices are presented in a uniformly random order. Assuming and are known in advance, we present a randomized exponential-time algorithm that colors any -colorable graph on vertices with colors in expectation. This is the first online coloring algorithm that uses a polylogarithmic number of colors for all fixed , and is better than a known lower bound of colors under adversarial arrivals for all fixed . In addition, assuming is known in advance, we obtain a competitive ratio of . For comparison, it is known to be NP-hard to approximate (offline) graph coloring within a factor of for all fixed . Therefore, our exponential-time online algorithm achieves a performance guarantee beyond the NP-hardness threshold for polynomial-time approximation algorithms.
Introduction
We study the online coloring problem, in which vertices are revealed one by one. When a vertex arrives, we must assign it a color immediately, before the next vertex arrives, so that its color differs from the colors of all its previously revealed neighbors. See Figure 1 for an example. This is one of the most extensively studied problems in online algorithms, alongside the -server problem, paging/caching, and online matching [4].
Figure 1. An example of online graph coloring. The numbers inside the vertices indicate their assigned colors. Vertices and edges drawn with gray dotted lines have not yet been revealed. The player must assign a color immediately when a vertex arrives.
Online Coloring
Online coloring is a classical problem for which natural algorithms are ineffective. The most intuitive strategy is First-Fit [11], which always chooses the smallest available color. However, First-Fit can use colors even on an -vertex bipartite graph, as shown in Figure 2 (such graphs are called crown graphs1). Accordingly, online coloring has been widely studied since the 1980s [25]. The best-known upper bounds on the competitive ratio are as follows: for randomized algorithms by Halldórsson [13] [13], and for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda [22] [22]. In contrast, a lower bound of is known due to Halldórsson and Szegedy [14] [14].
Figure 2. An -vertex bipartite graph on which First-Fit uses colors.
Given these strong negative results, online coloring of -colorable graphs for a fixed has received attention. For bipartite graphs (), a deterministic algorithm by Lovász, Saks, and Trotter [25] [25] achieves colors. The situation becomes much harder for : even for , the best-known results are a randomized -color algorithm by Vishwanathan [32] [32] and a deterministic -color algorithm by Kierstead [17] [17]. For comparison, the best-known lower bound is colors [32], leaving a substantial gap between the upper and lower bounds.
Online coloring is also studied for special graph classes, e.g., trees [6], interval graphs [20], planar graphs [15], bounded-treewidth graphs [5], and graphs of large odd girth [35]. See [16] for a survey on online coloring.
The Random-Order Model
The random-order model, which assumes that the input order is chosen uniformly at random, is widely studied in the context of online algorithms. The most well-known problem is arguably the secretary problem, in which candidates arrive for a job interview in random order, and the interviewer must decide immediately after each interview whether to hire the candidate. Only one candidate can be hired overall. Thanks to random arrivals, the classical secretary algorithm [23] selects the best candidate with probability at least . In contrast, under an adversarial arrival order, no algorithm can guarantee a success probability greater than . The random-order model also leads to improved performance in many other online problems, including the following examples (see [12] for a survey):
For the online bipartite matching problem, the optimal (tight) randomized competitive ratio is under adversarial arrivals [21]. However, under the random-order model, an algorithm achieves a competitive ratio of [27].
For the online knapsack problem, no algorithm can achieve a bounded competitive ratio under adversarial arrivals. However, under the random-order model, an algorithm achieves a competitive ratio of [18].
Online Coloring. In online coloring with random arrivals, the given graph is fixed, and the arrival order of the vertices is chosen uniformly at random from the possibilities, each with probability . This setting has been particularly well-studied for First-Fit.
For trees, First-Fit uses colors under adversarial arrivals [6, 11], but it drops to colors in expectation under the random-order model [10, 7].
For crown graphs (Figure 2), First-Fit uses colors under adversarial arrivals, but it drops to colors in expectation under the random-order model [34].
For general bipartite graphs, it was conjectured that First-Fit only uses polylogarithmic number of colors in the random-order model [7], but it is claimed to be disproved; a very recent preprint shows a lower bound of colors in expectation [24].
However, due to the inherent difficulty of online coloring, few studies have investigated random arrivals beyond First-Fit. In particular, it remained open whether algorithms for -colorable graphs could be improved under the random-order model; for example, whether an -color algorithm exists for -colorable graphs, which would improve upon the result of [32].
Our Contribution
In this paper, we show that the random-order model substantially improves the performance in online coloring: -colorable graphs can be colored online with a polylogarithmic number of colors for any constant . Formally, we prove the following main theorem.
Theorem 1. In the random-order model, when both and are known in advance, there exists a randomized online algorithm that colors any -colorable -vertex graph using colors in expectation.
This result significantly improves upon the previous -color bound [32]. In addition, for all fixed , our random-order result is better than the known lower bound of colors for adversarial arrivals [32]. Therefore, we establish the asymptotic separation between the random-order model and the adversarial-order model.
Moreover, assuming the result of the recent preprint [24], which claims that First-Fit uses expected colors for some bipartite graphs under random arrivals (and hence, for every , some -colorable graphs), our algorithm asymptotically outperforms First-Fit for all . Furthermore, we obtain a competitive ratio of , as stated in the following theorem.
Theorem 2. In the random-order model, when is known in advance, there exists a randomized online algorithm that attains a competitive ratio of .
Given the known lower bound of on the competitive ratio for adversarial arrivals [14], this also establishes the asymptotic separation between the random-order model and the adversarial-order model in terms of the competitive ratio. Note that our result assumes that is known in advance. This is a standard assumption in the random-order model; several previous studies [2, 3, 23, 31] also make the same assumption.
Online Algorithms vs. Approximation Algorithms
A broader question in theoretical computer science concerns the relationship between the competitive ratio in online algorithms and the approximation ratio in polynomial-time approximation algorithms. This topic is discussed in various studies [19, 26]. In general, if an online algorithm achieves a performance guarantee beyond the hardness barrier for polynomial-time approximation algorithms, then it must run in super-polynomial time.
As a matter of fact, online algorithms can achieve better performance guarantees than approximation algorithms for some problems, although we did not find any references that explicitly mention this observation. The work of Rubinstein [29] [29] presents an -competitive algorithm for the (maximum cardinality) secretary problem on a downward-closed set system. This immediately yields an -competitive algorithm for “online maximum independent set” with random arrivals. In contrast, approximating (offline) maximum independent set within a factor of is NP-hard for every fixed , as shown by Zuckerman [36] [36].
This paper gives an exponential-time -competitive algorithm for online coloring with random arrival order (Theorem 2), whereas approximating (offline) graph coloring within a factor of is NP-hard for every fixed [36]. Therefore, we establish the asymptotic separation between online and (deterministic or randomized) approximation algorithms in graph coloring, under the widely believed assumption that [1]. We note that, although a graph coloring can be obtained by repeatedly choosing a maximum independent set among the uncolored vertices, Rubinstein’s algorithm [29] does not directly imply an online coloring algorithm for random arrivals because the random arrival order on the uncolored vertices is not guaranteed.
Remark 3. Since the approximation side allows randomized algorithms, including random-order processing, we regard this comparison as fair. Moreover, our result achieves colors for 3-colorable graphs; however, no polynomial-time algorithm that colors 3-colorable graphs with colors is known at the time of writing.2
Overview of the Algorithm
In this subsection, we present an overview of our algorithm and the intuition behind using random arrival order. For simplicity, we consider the case here; the goal is to color a 3-colorable graph online with colors.
First, it suffices to devise an algorithm that colors the last vertices with colors, using information from the first vertices. If this can be done, we can color the entire graph with colors by recursively applying the same algorithm to the first vertices (for example, we color the -th vertices using information from the first vertices), using completely disjoint color sets for different levels of recursion. Here, we denote the set of the first vertices by .
The Benefit of Random Order. The benefit of random arrival order is that can be assumed to be chosen uniformly at random. Hence, we can assume that the two parts, and , have similar properties. For example, the sizes of maximum independent sets and the sizes of each color class in a 3-coloring are very similar.
In particular, for a sufficiently large independent set , the parts of that lie in and in do not differ much in size, with a statistical error of only . Therefore, after the first vertices have arrived, if we “sample” an independent set of , then it is likely that can be “extended” to the vertices in to the extent as large as . This mechanism allows us to obtain a large independent set in online.
Hardcore Sampling and Extension. After receiving all vertices in , we sample an independent set from the hardcore model [9, 33] with parameter , where is chosen with probability proportional to . As implied by the fact that a 3-colorable graph has an independent set of size at least , the expected size of is .
Then, the set of “eligible” vertices for extending the independent set toward is , which is sufficiently large by the discussion above.3 While itself may not be an independent set, it can be proven that most probably has maximum degree . See Figure 3 for an illustration. This implies that a large fraction of vertices in can be colored online using First-Fit with only colors.
Figure 3. Sampling an independent set from and attempting to extend it into .
Covering with Multiple Samples. The issue is that, with a single independent set , only a fraction of the vertices in are colored. We address this issue by carefully sampling a sequence of independent sets (), where is most probably . We also maintain “bins” for the extension counterpart, initially empty. For each arrival of , we find the smallest such that , and put into . Then, we can prove that each most probably has maximum degree . Hence, by applying First-Fit to each of , using a separate set of colors for each bin, we can most probably color the entire with colors.
Organization
§ 2 presents some formal definitions and notation. § 3 introduces the hardcore model and investigates its properties. § 4 introduces the main algorithm, and § 5 analyzes the number of colors used. § 6 presents an algorithm with a competitive ratio of . Finally, § 7 concludes the paper and presents some conjectures.
Preliminaries
Before moving on to our algorithms, we present the required notation and definitions. First, we formally define online coloring with random arrival order. Then, we define First-Fit, the most straightforward strategy for online coloring.
Definition 4 (Online Coloring). In the online coloring problem, an undirected graph is initially empty; i.e., there are zero vertices. The vertices of are given one by one. Immediately after a vertex arrives (along with all edges incident to previously arrived vertices), we must assign a color that differs from the colors of all adjacent vertices. The goal is to minimize the number of colors used, .
Definition 5 (Random-Order Model). The random-order model of online coloring assumes that a graph , where , is initially fixed and is hidden from the algorithm. We additionally assume that is known in advance. The vertices arrive in the order , where
is a permutation that is selected uniformly at random from possibilities, each with probability .
Definition 6 (First-Fit). First-Fit is an algorithm for online coloring that assigns each new vertex the smallest available color.
We use the following notation. Given a graph , we denote the set of vertices adjacent to as , and the set of vertices adjacent to at least one vertex in as . For a vertex set , we denote and . We denote the subgraph induced by as . We denote the chromatic number of as . We denote the set of all independent sets as . In -, -, and -notation, we write , , and to hide polylogarithmic factors in .
Hardcore Model
In this section, we discuss the properties of randomly sampled independent sets. We sample independent sets using the hardcore model [9, 33].
Definition 7 (Hardcore Model). Given a graph , the hardcore model with parameter is a probability distribution that chooses an independent set with probability proportional to . More precisely, define
Then, an independent set is chosen with probability . See Figure 4 for an example.
Figure 4. An example of the hardcore model, with the probability of selecting each independent set.
Basic Properties
First, we present some properties of the hardcore model that are used in the subsequent proofs.
Proposition 8. Let , and let be a -colorable graph. Then,
Proof. For the upper bound, by the binomial theorem. For the lower bound, since has a -coloring, one color class has size at least , so it contains an independent set with . By the binomial theorem,
Proposition 9. Let , and let be a graph. For disjoint vertex sets (),
Proof. Each can be written as , where and . Therefore, . By Proposition 8, we have , which proves the desired inequality.
The Size of Independent Sets
We analyze the expected size of an independent set. Note that the case was already studied by Nilli [28] [28], who showed that the average size of independent sets for a -colorable graph is and proved that this bound is tight.
Lemma 10. Let , and let be a -colorable graph. Then,
Proof. First, the function is convex, so it follows from Jensen’s inequality that:
The last inequality is due to Proposition 8. Therefore:
The last inequality follows from for all .
The Neighborhood Structures
We also investigate the structure surrounding a random independent set . In the following two lemmas, we analyze the expected size of .
Lemma 11. Let , and let be a graph. Then,
Proof. Fix . Let , and . Then, the relationship holds (Figure 5), as shown below:
Figure 5. The definitions of and , and the bijection between them.
For every , because is an independent set due to .
For every , because is an independent set and .
Here, for each , the probability that is chosen is times the probability that is chosen. Therefore,
Equivalently,
Summing this equation over all , we have by linearity of expectation.
Lemma 12. Let , and let be a -colorable graph. Then,
Proof. By Lemma 11, . Thus, by Lemma 10,
The Algorithm
We present an algorithm that colors -colorable graphs online with colors in the random-order model. The intuition is already given in Subsection 1.5. Note that, in the subsequent sections, we use to denote the current graph for the algorithm and to denote the final graph, as in Definition 5.
Basic Strategy
We consider developing an algorithm that colors the last vertices using colors, given that the first vertices have already arrived and have been colored. If this can be done, we can recursively apply the same algorithm to the first vertices. Then, we can color the entire graph with colors.
However, for convenience in the analysis, we do not exactly divide them into vertices each. Instead, we sample from a binomial distribution , and we color the last vertices, given that the first vertices have already arrived. We note that is very close to (with error), so this does not fundamentally change the algorithm. We use disjoint colors for the first vertices and the last vertices. Let be the set of the first vertices. Under this framework, is uniformly distributed over the subsets of , as shown below.
Lemma 13. Let . Let be the set of the first vertices. Then, each subset of appears as with probability exactly .
Proof. The probability that is by the binomial distribution. Also, there are possible subsets of with size , and all of them have equal probabilities of appearing as because of the random-order model. Hence, Lemma 13 holds. □
Algorithm Details
Now, we consider an algorithm to color the last vertices . The algorithm consists of two phases: (1) the learning phase, which learns and extracts the structure of the first vertices, and (2) the output phase, which actually colors the last vertices by exploiting the learned structure. The two phases are described as follows.
(1) The Learning Phase. The core idea is that, if we sample an independent set , many vertices in are likely to have no neighbor in thanks to the random arrivals (Subsection 1.5). Such a set of vertices can be colored efficiently, as we prove in § 5. However, a single sampled independent set does not cover all vertices in . Therefore, we need to sample multiple independent sets.
In the algorithm, we sample a sequence of independent sets , each from a hierarchy . We start with . For in this order, we sample an independent set from , and then we let . See Figure 6 for an example. Eventually, becomes empty; we let be the first index such that . When coloring the remaining vertices, we use independent sets . It can be proven that with high probability (Lemma 16), regardless of the value of the parameter .
Figure 6. An example of the learning phase.
(2) The Output Phase. Next, we color the remaining vertices. Here, we maintain bins , initially empty, which correspond to , respectively.
When a vertex arrives, we put into for the smallest such that . Such an must exist because . Although is not necessarily an independent set, it can be proven that the maximum degree of is with high probability in the range of (Lemma 21). Hence, with the parameter setting
all have maximum degrees with high probability (Lemma 22). Therefore, we can use the First-Fit algorithm to color each vertex of . We use disjoint sets of colors for bins .
Overall Algorithm. The pseudocode for the entire algorithm is presented in Algorithm 1. With high probability, we use colors for each , and . Therefore, we use colors in expectation for the last vertices (Lemma 23). We analyze the algorithm’s performance in detail in the next section.
Remark 14. The runtime of Algorithm 1 is unbounded for the scenario where is chosen every time. However, if , the only thing that happens is a call to the identical procedure . Therefore, the outcome of Algorithm 1 remains the same if we choose from the distribution that excludes , i.e., each is chosen with probability ; this change makes its runtime bounded. Note that is also bounded; we will prove in Lemma 15. Nevertheless, this algorithm runs in exponential time, because sampling an independent set from takes exponential time.
Analysis
In this section, we analyze the performance of Algorithm 1.
Number of Levels
First, we analyze the number of sampled independent sets: we prove that this is surely at most and is with high probability.
Algorithm 1 COLORINGₖ(n): An algorithm to color an n-vertex graph online.
1: λ ← 1/(6k ln(3k) ln n + 2)
2: m ∼ Binomial(n, 1/2)
3: Color the first m vertices with COLORINGₖ(m), if m ≥ 1
4: S ← the set of the first m vertices
5: A₁ ← S; r ← 1
6: loop
7: Iᵣ ← IS_λ(G[Aᵣ])
8: if Iᵣ = ∅ then
9: break
10: Aᵣ₊₁ ← N_{Aᵣ}(Iᵣ)
11: r ← r + 1
12: J₁, …, Jᵣ ← ∅
13: for each arrival of the remaining vertices v ∈ V* \ S do
14: i ← the smallest i such that N_{Iᵢ}(v) = ∅
15: Jᵢ ← Jᵢ ∪ {v}, and color v using First-Fit on G[Jᵢ]
Lemma 15. .
Proof. Since Algorithm 1 ensures that and contains no vertex of for each , it follows that . Since , we have .
Lemma 16. Suppose that . For all possible inputs of the first vertices,
Proof. Fix an arbitrary realization of . By applying Lemma 12 to , we have
Taking expectations over , we obtain . Since ,
Since for all , we have with . Since is a non-negative integer, Markov’s inequality implies that is empty with probability at least . Moreover, if is empty, then is also empty, meaning that . Therefore, with probability at least .
Maximum Degrees
Next, we analyze the maximum degrees of the subgraphs . Specifically, we show that the maximum degrees of are with high probability.
Introducing the History Sequence
Here, for a given graph , we need to analyze all possibilities for the first vertices and the sampled independent sets. The outcome of Algorithm 1 in terms of coloring the last vertices, i.e., , is determined by . To this end, we define history sequences as follows.
Definition 17 (History Sequence). Let be an integer. Given a graph , the “history sequence up to level ” is defined as a sequence . This is defined even when ; in this case, when . The set of all possible history sequences up to level is denoted as
It is easy to see that indeed enumerates all history sequences with positive probability.
Proposition 18. Let be an integer. The probability that the history sequence up to level equals is given by
Proof. The probability that is chosen is by Lemma 13. The probability that is chosen from is by the definition of the hardcore model (note that this probability is 1 for ). Thus, Proposition 18 holds. □
Degree Analysis with Double-Counting Method
To establish the maximum degree bound, we prove the following lemma using the double-counting method on history sequences.
Lemma 19. Let be the parameter of the hardcore model. Suppose is a fixed -colorable graph. For every vertex and every integer ,
Proof. Let be the set of all history sequences up to level in which the vertex is put into . For each , define the following:
Let be the set of vertices adjacent to in .
Let be an arbitrary maximum independent set of .
Since is -colorable, we have . Moreover, each subset is also an independent set (see Figure 7). Therefore, we can write down history sequences as follows (we add to each of and to ):
Figure 7. An illustration of the sets , , and used to construct a new history sequence .
for each .
The sequence is indeed a valid history sequence up to level . This can be shown as follows. First, for every , is an independent set of , because is an independent set of . Second, holds, because if some vertex has no neighbor in , then should have been put into bin instead of . Third, is an independent set because is an independent set and every vertex in has no neighbor in .
Next, the constructed histories , over all and , are pairwise distinct. This is because, from a history sequence , we can uniquely recover as , and hence we can also uniquely recover the original history sequence . The reason for is that, for , each vertex in is not adjacent to (due to ), but each vertex in is adjacent to (due to ). Therefore, the total probability of all history sequences is at most 1:
On the other hand, we also have a lower bound on the probability in terms of . This is calculated as follows:
The first equality is derived from Proposition 18, and the inequality is derived from Proposition 9. Therefore, by the binomial theorem, we obtain
Combining Equation (1), Equation (2), and , we obtain
Lemma 19 follows directly from this inequality. □
Deriving the Degree Bound
Lemma 20. Let be the parameter of the hardcore model. Suppose is a fixed -colorable graph. For every vertex and every positive integer ,
Proof. First, for every positive integer , we have
Therefore, Lemma 19 implies that the following inequality also holds for :
By Markov’s inequality, Equation (4) implies . By taking the logarithm of both sides, the condition above becomes
Here,
This is due to for all . Therefore, combining Equation (5) and Equation (6), the probability that and is at most . □
Lemma 21. Let be the parameter of the hardcore model, and let be a positive integer. Suppose is a fixed -colorable graph. The probability that the maximum degree of exceeds is at most .
Proof. The maximum degree of exceeds only if the event of Equation (3) occurs for at least one . Hence, by Lemma 20 and the union bound, this probability is at most . □
Lemma 22. With , for every fixed -colorable graph , all have maximum degrees at most with probability at least .
Proof. We apply Lemma 21 with parameter . That is, for each , the maximum degree of exceeds with probability at most . Hence, the probability that both of the following conditions hold:
, and
at least one of has maximum degree more than
is at most by the union bound and the fact that (Lemma 15). Excluding the case , which happens with probability at most (Lemma 16), Lemma 22 follows. □
The Grand Finale
Finally, we analyze the total number of colors used in Algorithm 1.
Lemma 23. In Algorithm 1, the number of colors used for is in expectation.
Proof. If the maximum degrees in are at most , then First-Fit uses at most colors, resulting in at most colors for the entire . Therefore, by Lemma 16, Lemma 22, and the union bound, we use at most colors with probability at least . In the remaining case, which occurs with probability at most , we may use up to colors, but this is negligible. □
Lemma 24. The number of calls to in Algorithm 1 is at most with probability at least .
Proof. By Lemma 13, each vertex is put into , i.e., colored in the recursion, with probability . Hence, each vertex goes down for at least recursions with probability at most . If this does not happen for any , then the recursion depth in Algorithm 1 is at most . By the union bound, this occurs with probability at least . □
We are now ready to prove our main theorem, which shows that Algorithm 1 uses at most colors in expectation.
Theorem 1 (restated). In the random-order model, when both and are known in advance, there exists a randomized online algorithm that colors any -colorable -vertex graph using colors in expectation.
Proof. For each call to , we use colors in expectation, due to Lemma 23. Note that we can assume random arrivals in each call to , because does not depend on the graph structure (i.e., it depends only on random choices), and the probability of this event does not change by shuffling the order of the first vertices, due to the random-order assumption in the original graph .
Hence, across the shallowest calls to (or all calls if there are fewer), we use colors in expectation. If there are more than calls, at most colors may be used, but this probability is at most (Lemma 24), so this is negligible. □
The Competitive Ratio
We consider online coloring with random arrivals for general graphs. In online coloring, a lower bound of on the competitive ratio is known for both deterministic and randomized algorithms [14]. However, with the random-order model, we can do better.
Theorem 2 (restated). In the random-order model, when is known in advance, there exists a randomized online algorithm that attains a competitive ratio of .
Proof. The idea is to simulate the behavior of Algorithm 1 for -colorable graphs, , on the same input graph , for each in parallel processes. We assume disjoint sets of colors for different processes. For each arrival of vertex , we color using the color selected by the process that has used the fewest colors so far.
We now analyze the number of colors used. Let . Since is -colorable, by Theorem 1, the number of colors used by the process with , denoted by , satisfies
Moreover, for each process, at most colors are used in the actual online coloring, so the number of colors used overall is at most . Therefore, this algorithm uses colors in expectation. Also, it is obvious that we use at most colors. Thus, we attain a competitive ratio of , with the worst-case bound attained when
Conclusion
In this paper, we presented an algorithm for online coloring with random arrivals that uses colors for -colorable graphs. For online coloring as a whole, we improved the performance for the case from colors [32] to colors. We also achieved a competitive ratio of , which is better than the conventional lower bound [14] and is better than an inapproximability bound for graph coloring [36]. These results demonstrate that the random-order model unlocks new possibilities for improving the performance of online coloring algorithms. It is now natural to pose the following conjectures.
Conjecture 25. In the random-order model, when both and are known in advance, there exists a randomized online algorithm that colors any -colorable -vertex graph using colors in expectation.
Conjecture 26. In the random-order model, when is known in advance, there exists a randomized online algorithm that attains a competitive ratio of .
Finally, a limitation of our result is that it relies on the random-order model and does not extend to adversarial arrivals. It is natural to ask whether the following conjecture holds.
Conjecture 27. For any constant , there exists a (randomized) online algorithm for coloring -colorable graphs with colors, even without assuming random arrivals.
Acknowledgements
We are grateful to our professor Ken-ichi Kawarabayashi for helpful discussions and comments. We also thank Yuta Inoue for his feedback on the Introduction section.
AI Usage Disclosure
The authors substantially used OpenAI’s large language model, GPT-6 Astra, during the proof exploration phase. Through an iterative process with the authors, the model generated the proof of the main theorem (Theorem 1) for the special case . Then, the authors simplified the proof, discussed and obtained the intuition behind the algorithm, and generalized the analysis to all . The authors also used GPT-6 Astra and GPT-5.6 Sol to polish the paper’s presentation. The authors take full responsibility for the correctness and content of the paper.
References
- [1]Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press Cambridge, 2009.
- [2]Susanne Albers and Maximilian Janke. “Scheduling in the Secretary Model”. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Vol. 213. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 6:1–6:22. DOI: 10.4230/LIPIcs.FSTTCS.2021.6.DOI
- [3]Susanne Albers, Arindam Khan, and Leon Ladewig. “Improved Online Algorithms for Knapsack and GAP in the Random Order Model”. In: Algorithmica 83.6 (2021), pp. 1750–1785. DOI: 10.1007/s00453-021-00801-2.DOI
- [4]Susanne Albers. “Online algorithms: a survey”. In: Mathematical Programming 97.1 (2003), pp. 3–26.DOI
- [5]Susanne Albers and Sebastian Schraink. “Tight bounds for online coloring of basic graph classes”. In: Algorithmica 83.1 (2021), pp. 337–360.arxiv.org/abs/1702.07172
- [6]Dwight R Bean. “Effective coloration”. In: The Journal of Symbolic Logic 41.2 (1976), pp. 469–480.DOI
- [7]Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło. “First-Fit Coloring of Forests in Random Arrival Model”. In: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Ed. by Rastislav Královič and Antonín Kučera. Vol. 306. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 33:1–33:10. ISBN: 978-3-95977-335-5. DOI: 10.4230/LIPIcs.MFCS.2024.33. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.33.DOI
- [8]Nikhil Bansal, Neng Huang, and Euiwoong Lee. Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs. 2026. arXiv: 2602.05904. URL: https://arxiv.org/abs/2602.05904.
- [9]Ewan Davies and Ross J Kang. The hard-core model in graph theory. 2025. arXiv: 2501.03379. URL: https://arxiv.org/abs/2501.03379.
- [10]Fabian Frei, Matthias Gehnen, Dennis Komm, Rastislav Královič, Richard Královič, Peter Rossmanith, and Moritz Stocker. Tree coloring: Random order and predictions. 2024. arXiv: 2405.18151. URL: https://arxiv.org/abs/2405.18151.
- [11]András Gyárfás and Jenő Lehel. “On-line and first fit colorings of graphs”. In: Journal of Graph Theory 12.2 (1988), pp. 217–227.DOI
- [12]Anupam Gupta and Sahil Singla. “Random-Order Models”. In: Beyond the Worst-Case Analysis of Algorithms. Ed. by Tim Roughgarden. Cambridge University Press, 2021, pp. 234–258. doi: 10.1017/9781108637435.015.DOI
- [13]Magnús M Halldórsson. “Parallel and On-Line Graph Coloring”. In: Journal of Algorithms 23.2 (1997), pp. 265–280. issn: 0196-6774. doi: 10.1006/jagm.1996.0836. URL: https://www.sciencedirect.com/science/article/pii/S0196677496908366.DOI
- [14]Magnús M Halldórsson and Mario Szegedy. “Lower bounds for on-line graph coloring”. In: Theoretical Computer Science 130.1 (1994), pp. 163–174. doi: 10.1016/0304-3975(94)90157-0.
- [15]Sandy Irani. “Coloring inductive graphs on-line”. In: Algorithmica 11.1 (1994), pp. 53–72.
- [16]Hal A Kierstead. “Coloring graphs on-line”. In: Online algorithms: the state of the art. Springer, 2005, pp. 281–305.
- [17]Henry A Kierstead. “On-line coloring k-colorable graphs”. In: Israel Journal of Mathematics 105.1 (1998), pp. 93–104.
- [18]Max Klimm and Martin Knaack. “Generalized assignment and knapsack problems in the random-order model”. In: Mathematical Programming (2026). doi: 10.1007/s10107-026-02405-6.DOI
- [19]Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. “Playing games with approximation algorithms”. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007, pp. 546–555.
- [20]Henry A Kierstead and William T Trotter. “An extremal problem in recursive combinatorics”. In: Congressus Numerantium 33 (1981), pp. 143–153.
- [21]Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. “An optimal algorithm for on-line bipartite matching”. In: Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990, pp. 352–358.DOI
- [22]Ken-ichi Kawarabayashi, Hirotaka Yoneda, and Masataka Yoneda. Online Graph Coloring for k-Colorable Graphs. 2025. arXiv: 2511.16100 [cs.DS]. URL: https://arxiv.org/abs/2511.16100.
- [23]Denis V Lindley. “Dynamic programming and decision theory”. In: Journal of the Royal Statistical Society: Series C (Applied Statistics) 10.1 (1961), pp. 39–51.DOI
- [24]Yaqiao Li and Xin Li. FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model. 2026. arXiv: 2610.15468 [cs.DS]. URL: https://arxiv.org/abs/2610.15468.
- [25]László Lovász, Michael Saks, and William T. Trotter. “An on-line graph coloring algorithm with sublinear performance ratio”. In: Discrete Mathematics 75.1–3 (1989), pp. 319–325.
- [26]Esther Mohr, Iftikhar Ahmad, and Günter Schmidt. “Online algorithms for conversion problems: a survey”. In: Surveys in Operations Research and Management Science 19.2 (2014), pp. 87–104.
- [27]Mohammad Mahdian and Qiqi Yan. “Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs”. In: Proceedings of the forty-third annual ACM symposium on Theory of computing. 2011, pp. 597–606.
- [28]Alon Nilli. “The average size of an independent set in graphs with a given chromatic number”. In: Journal of Combinatorial Theory, Series B 45.1 (1988), pp. 112–114.
- [29]Aviad Rubinstein. “Beyond matroids: Secretary problem and prophet inequality with general constraints”. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016, pp. 324–332.arxiv.org/abs/1604.00357
- [30]Zhao Song. An O(n^{1/6})-Coloring Algorithm for 3-Colorable Graphs. SSRN working paper. 2026. DOI: 10.2139/ssrn.7551399. URL: https://ssrn.com/abstract=7551399.DOI
- [31]Richard Santiago, Ivan Sergeev, and Rico Zenklusen. “Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid”. In: Mathematical Programming 210.1–2 (2025), pp. 815–846. DOI: 10.1007/s10107-024-02177-x.DOI
- [32]Sundar Vishwanathan. “Randomized online graph coloring”. In: Journal of Algorithms 13.4 (1992), pp. 657–669.
- [33]Dror Weitz. “Counting independent sets up to the tree threshold”. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006, pp. 140–149.DOI
- [34]Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, and Yaqiao Li. FirstFit online coloring in the random order model. 2026. arXiv: 2608.29603. URL: https://arxiv.org/abs/2608.29603.
- [35]Hirotaka Yoneda and Masataka Yoneda. “Online Coloring for Graphs of Large Odd Girth”. In: 34th Annual European Symposium on Algorithms (ESA 2026). 2026, 127:1–127:15.
- [36]David Zuckerman. “Linear degree extractors and the inapproximability of max clique and chromatic number”. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. 2006, pp. 681–690.






