betaFeedback

WorksComputer Science

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of Ω(n/log⁡2n)Ω(n / \log^2 n) for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of O(n/log⁡n)O(n / \log n) for randomized algorithms by Halldórsson (1997), and (3) an upper bound of O(n/log⁡log⁡n)O(n / \log \log n) for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of Ω(n/log⁡n)Ω(n / \log n) for deterministic algorithms. 2. A new upper bound of O(n(log⁡log⁡n)2/log⁡2n)O(n (\log \log n)^2 / \log^2 n) for randomized algorithms. 3. A new upper bound of O(n/(log⁡log⁡n)2−ε)O(n / (\log \log n)^{2-\varepsilon}) for deterministic algorithms for every fixed ε>0\varepsilon>0. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only O((log⁡log⁡n)2)O((\log \log n)^2). We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

Introduction

A central problem both in discrete math and in theoretical computer science, graph coloring, is to color each vertex of a given graph G=(V,E)G=(V,E) with as few colors as possible so that no two adjacent vertices have the same color. We study the online coloring problem, the online version of graph coloring, in which the vertices are given one by one (together with their incident edges). Immediately after a vertex arrives, we must assign it a color before the next vertex arrives. Once the color is assigned, it cannot be changed. Online coloring is one of the most central questions in online algorithms, alongside online matching, kk-server, and the list update problem [3].

Historical Background

Historically, the central focus in the study of online algorithms has been competitive analysis, which compares an online algorithm’s performance to that of an optimal offline algorithm. This is also the case in online coloring; the competitive ratio1 for online coloring was studied as early as the 1980s [14, 25]. However, straightforward algorithms perform poorly. For example, the First-Fit algorithm, which always chooses the smallest available color, has a competitive ratio of at least n/4n/4 (for graphs with nn vertices), as it may use n/2n/2 colors even on a bipartite graph (Figure 1). This makes online coloring particularly challenging compared to other online problems.

Figure 1. A worst-case bipartite graph on which First-Fit uses n/2n/2 colors.

Competitive ratio. As one of the most important results in online coloring, Halldórsson and Szegedy [17] [17] presented a lower bound of Ω(n/log⁡2n)\Omega(n/\log^2 n) on the competitive ratio. This shows the inherent difficulty of online coloring. However, a central question remains: “Do randomized algorithms outperform deterministic algorithms in online coloring?”

Deterministic vs. randomized. On the deterministic side, Lovász, Saks, and Trotter [25] [25] found an algorithm with a competitive ratio of O(n/log⁡∗n)O(n/\log^* n), followed by improvements to O(nlog⁡log⁡log⁡n/log⁡log⁡n)O(n\log\log\log n/\log\log n) by Kierstead (1998) [21] and to O(n/log⁡log⁡n)O(n/\log\log n) by Kawarabayashi, Yoneda, and Yoneda in 2025 [23] (to appear in SODA ’27). On the randomized side, Vishwanathan [29] [29] found an algorithm with a competitive ratio of O(n/log⁡1/2n)O(n/\log^{1/2} n), and improved to O(n/log⁡n)O(n/\log n) by Halldórsson [16] [16]. We assume an oblivious adversary for randomized algorithms, where the input is fixed independently of the algorithm’s output.

Although the best-known randomized upper bound is better than the deterministic one, the asymptotic separation between the optimal competitive ratios remains open because the best-known lower bounds for both are Ω(n/log⁡2n)\Omega(n/\log^{2} n); see Figure 2. Whether an asymptotic separation exists is crucial not only for online coloring but also for the broader field of online algorithms. In the worst-case analysis of deterministic algorithms, we must assume an “adversarial attack”, which has also been studied in the context of machine learning, such as in the adversarial bandit problem [1]. Therefore, settling the existence question would clarify whether the adversary is effective. Note that an asymptotic separation has been established for many online problems, such as online caching [12] and the kk-server problem in general metric spaces [26, 6, 27].

Figure 2. The previously known lower and upper bounds for randomized and deterministic algorithms. These bounds do not establish an asymptotic separation.

Positioning. Online coloring has a deep connection with structural graph theory in general, as many algorithmic improvements are made by exploiting novel subgraph structures [29, 23 BFS+26, 30]. This problem has also been studied in the context of informational hardness [15, 5] and parallel and distributed computing [16 AEL+23]. Moreover, online coloring can be applied to scheduling [11], resource allocation [19], and cloud computing [28].

Related work. In online coloring, researchers have studied a wide range of topics beyond the competitive ratio. The first topic is online coloring for kk-colorable graphs (for a constant k≥2k \ge2). On the deterministic side, Kierstead [21] presented an algorithm that uses O~(n1−1/k!)\widetilde{O}(n^{1-1/k!}) colors, and recently Kawarabayashi, Yoneda, and Yoneda [23] improved the bound to O~(n1−2/(k(k−1)))\widetilde{O}(n^{1-2/(k(k-1))}) colors. On the randomized side, Vishwanathan [29] found an algorithm that uses O~(n1−1/(k−1))\widetilde{O}(n^{1-1/(k-1)}) colors. A large gap remains to the best-known lower bound of Ω(log⁡k−1n)\Omega(\log^{k-1} n) colors [29].2

The second topic is online coloring for special graph classes. Kierstead and Trotter [22] presented a 3-competitive online coloring algorithm for interval graphs. Trees [7, 14], bipartite graphs [25, 5, 13], planar graphs [18], and bounded-treewidth graphs [4] can be colored online using Θ(log⁡n)\Theta(\log n) colors. For every fixed ε>0\varepsilon> 0, an O(nε)O(n^{\varepsilon})-color algorithm exists for graphs with sufficiently large odd girth [30]. First-Fit performs well on dd-degenerate graphs; it uses only O(dlog⁡n)O(d\log n) colors. For more results, see the survey by Kierstead [20].

A related, recently well-studied topic is online edge coloring, in which we must color edges that arrive one by one. Edge coloring is easier than vertex coloring: a (1+o(1))(1+o(1))-competitive algorithm is known for graphs with maximum degree Δ=ω(log⁡n)\Delta= \omega(\log n) [9 BSV+25].

Our Contributions

In this paper, we improve the bounds on competitive ratios from three sides, as stated below.

Theorem 1.1. Every deterministic online coloring algorithm is Ω(n/log⁡n)\Omega(n/\log n)-competitive.

Theorem 1.2. There exists a polynomial-time randomized online coloring algorithm, against an oblivious adversary, that attains a competitive ratio of O(n(log⁡log⁡n)2/log⁡2n)O(n(\log\log n)^2/\log^2 n).

Theorem 1.3. For every fixed ε>0\varepsilon> 0, there exists a polynomial-time deterministic online coloring algorithm that attains a competitive ratio of O(n/(log⁡log⁡n)2−ε)O(n/(\log\log n)^{2-\varepsilon}).

These results represent the first substantial improvements since the 20th century. Theorem 1.1 improves on Halldórsson and Szegedy [17] [17]. Theorem 1.2 improves on Halldórsson [16] [16]. Theorem 1.3 is the first poly(log⁡log⁡n)(\log\log n)-factor improvement since Kierstead (1998) [21]. See Figure 3 for a comparison. Consequently, the gap between the upper and lower bounds for the randomized case is almost closed; only a factor of O((log⁡log⁡n)2)O((\log\log n)^2) remains.

Historical improvements in the upper and lower bounds for randomized and deterministic algorithms

Figure 3. Historical improvements in the upper and lower bounds for randomized (left) and deterministic (right) algorithms.

Importantly, Theorems 1.1 and 1.2 show that randomization gives an asymptotic advantage in online graph coloring. Every deterministic algorithm has worst-case competitive ratio Ω(n/log⁡n)\Omega(n/\log n), whereas our randomized algorithm achieves expected competitive ratio o(n/log⁡n)o(n/\log n) against an oblivious adversary. The distinction is visible even on graphs that can be colored offline with O(log⁡n)O(\log n) colors. For every deterministic algorithm, there is an input where no color is used more than twice, forcing the algorithm to use at least n/2n/2 colors. In contrast, on every fixed input in this class, our randomized algorithm uses o(n)o(n) colors in expectation.

In addition, to obtain Theorem 1.3, we develop a better deterministic online coloring algorithm for graphs without rr-cliques: our algorithm uses O(n(log⁡log⁡n/log⁡n)1/(r−2))O(n(\log\log n/\log n)^{1/(r-2)}) colors for every constant r≥3r \ge3 (Remark 6.7). The best previously known deterministic algorithm by Bradač et al. [8] [BFS+26] uses O(nlog⁡(r−1)n/log⁡(r−2)n)O(n\log^{(r-1)}n/\log^{(r-2)}n) colors, where log⁡(j)n\log^{(j)}n denotes the jj-fold iterated logarithm.

Improvements on Larger Chromatic Numbers

Beyond the competitive analysis, our results also improve performance and hardness for online coloring of graphs with larger chromatic numbers by a significant margin.

Historically, competitive analysis in online coloring has focused on improving algorithmic performance on graphs with small chromatic numbers, particularly kk-colorable graphs for a constant k≥3k \ge3. For the randomized side, an O~(n1−1/(k−1))\tilde{O}(n^{1-1/(k-1)})-color algorithm [16] yielded an O(n/log⁡n)O(n/\log n)-competitive algorithm. For the deterministic side, an O~(22k+3n1−2/(k(k−1)))\tilde{O}(2^{2^{k+3}}n^{1-2/(k(k-1))})-color algorithm [23] yielded an O(n/log⁡log⁡n)O(n/\log\log n)-competitive algorithm. However, we take the opposite approach, targeting graphs with large and middle-tier chromatic numbers.

Large-Chromatic Approach (Theorem 1.1 and Theorem 1.2)

In Theorem 1.1 and Theorem 1.2, we consider online coloring of graphs with a large chromatic number kk, for example, when k=nck=n^c for some c>0c>0. To start, consider Algorithm 1, which uses each color on at most two vertices and, whenever possible, uses a color already used exactly once. This algorithm is somewhat effective when kk is large; when k=o(n)k=o(n), it uses only n/2+o(n)n/2+o(n) colors, and only an o(1)o(1) fraction of the colors appear on exactly one vertex.

Proposition 1.4. Let n,k≥1n,k\ge1 be integers. For a nn-vertex graph without (k+1)(k+1)-cliques, Algorithm 1 uses at most n+k2\frac{n+k}{2} colors. Also, the same bound trivially holds for kk-colorable graphs.

Proof. Let v1,…,vtv_1,\ldots,v_t be the vertices whose colors are used exactly once. These vertices must form a clique, because if viv_i and vjv_j are not adjacent for some i,ji,j (i<ji<j), then vjv_j would have been colored with the same color as viv_i, a contradiction. Hence, t≤kt\le k by assumption. Since all other colors are used exactly twice, the algorithm uses t+n−t2=n+t2≤n+k2t+\frac{n-t}{2}=\frac{n+t}{2}\le\frac{n+k}{2} colors. □

Since Algorithm 1, which uses at most two vertices per color, performs well for large chromatic numbers kk, a natural question arises: “Can this approach be extended to three vertices per color?” The answer is no for deterministic algorithms but yes for randomized algorithms.

For every deterministic algorithm, there exists an Θ(log⁡n)\Theta(\log n)-colorable graph on which the algorithm uses each color on at most two vertices and hence uses at least n/2n/2 colors, as we will prove in § 4. This is how we derive an Ω(n/log⁡n)\Omega(n/\log n) lower bound.

In contrast, for randomized algorithms, our new algorithm colors any kk-colorable graph with expected n/3+o(n)n/3+o(n) colors when k=o(n1/2)k=o(n^{1/2}), as we prove in Subsection 5.3. In general, for every integer t≥2t\ge2, there exists a randomized algorithm that colors any kk-colorable graph with expected n/t+o(n)n/t+o(n) colors when k=o(n1/(t−1))k=o(n^{1/(t-1)}). Figure 4 (left) shows the performance by the chromatic

Figure 4. Performance frontiers for online coloring by chromatic number kk, for randomized and deterministic algorithms. The previous results are shown in blue, and our results are shown in red.

Algorithm 1 An algorithm for online coloring.

1:  for each arrival of a vertex v do
2:      if there exists a color c that is used exactly once and is not adjacent to v then
3:          Color v with color c
4:      else
5:          Color v with a new color

number kk. Roughly speaking, the frontier of Halldórsson’s algorithm [16] is tk−1≈nt^{k-1} \approx n, while the frontier of our algorithm is kt−1≈nk^{t-1} \approx n, crossing at k=t=Θ(log⁡n/log⁡log⁡n)k=t=\Theta(\log n/\log\log n). This is why combining them attains a competitive ratio of O(n(log⁡log⁡n/log⁡n)2)O(n(\log\log n/\log n)^2).

Mid-Chromatic Approach (Theorem 1.3)

To improve deterministic algorithms (Theorem 1.3), we cannot take the large-chromatic approach due to the negative lower-bound result. Instead, we take a different approach that focuses on a regime of “moderate” chromatic numbers kk; see Figure 4 (right). For background, Kawarabayashi, Yoneda, and Yoneda’s deterministic algorithm [23] uses Ω((log⁡log⁡n)1−ε/2)\Omega((\log\log n)^{1-\varepsilon/2}) vertices per color3 in the regime of k∈[1,(log⁡log⁡n)1−ε/2]k \in[1,(\log\log n)^{1-\varepsilon/2}].

In this paper, we also achieve equivalent performance for k∈[(log⁡log⁡n)1−ε/2,(log⁡log⁡n)2−ε]k \in[(\log\log n)^{1-\varepsilon/2},(\log\log n)^{2-\varepsilon}]. We make this possible by upgrading their algorithm with our new technical framework based on clique-free graphs; this is the main technical contribution of this paper. Using this approach, we attain a competitive ratio of O(n/(log⁡log⁡n)2−ε)O(n/(\log\log n)^{2-\varepsilon}).

Organization

Section 2 presents technical overviews of each algorithm. Section 3 presents formal definitions and fundamental lemmas used in our proofs. Section 4 presents an Ω(n/log⁡n)\Omega(n/\log n) lower bound for the competitive ratio of deterministic online coloring (Theorem 1.1). Section 5 presents an O(n(log⁡log⁡n)2/log⁡2n)O(n(\log\log n)^2/\log^2 n)-competitive algorithm for randomized online coloring (Theorem 1.2). Section 6 presents an O(n/(log⁡log⁡n)2−ε)O(n/(\log\log n)^{2-\varepsilon})-competitive algorithm for deterministic online coloring (Theorem 1.3). Finally, Section 7 concludes the paper with conjectures.

Technical Overview

Theorem 1.1: The Lower Bound for Deterministic Algorithms

In the worst-case analysis of deterministic online algorithms, we can assume that an adversary determines the neighbors of each new vertex vv based on the algorithm’s current output. To this end, we develop a strategy for the adversary that forces every (online) color to be used on at most two vertices. For a 2ℓ2\ell-colorable graph (ℓ≥1\ell\ge1), we achieve this goal through 2ℓ2^\ell vertices.

Transparent model. Halldórsson and Szegedy [17] proved an Ω(n/log⁡2n)\Omega(n/\log^2 n) lower bound based on the transparent model, in which the adversary maintains a (proper) 2ℓ2\ell-coloring φ:V→{1,…,2ℓ}\varphi: V \to\{1,\ldots,2\ell\} in real time. Immediately after the algorithm colors a vertex vv, the adversary must irrevocably assign φ(v)∈{1,…,2ℓ}\varphi(v) \in\{1,\ldots,2\ell\}, called a base color (to distinguish it from the “colors” that the algorithm assigns). We assume that the coloring φ\varphi is visible to the algorithm. While this model simplifies the analysis, the adversary cannot force every (online) color to appear on at most two vertices for more than 4ℓ2+2ℓ4\ell^2 + 2\ell vertices (Subsection 4.1).

New adversary. We modify the transparent model as follows. For the first vertex v1v_1 of a color, the adversary does not assign the base color φ(v1)\varphi(v_1). For the second vertex v2v_2 of this color, they must assign the base colors φ(v1)\varphi(v_1) and φ(v2)\varphi(v_2) simultaneously. Here, we impose one rule: the adversary must assign the base color 2i−12i-1 to one of them and 2i2i to the other, for some i∈{1,…,ℓ}i \in\{1,\ldots,\ell\}.

When the adversary decides the neighbors of each vertex vv, they choose a set Xv⊆{1,…,2ℓ}X_v \subseteq\{1,\ldots,2\ell\} such that exactly one of 2i−12i-1 and 2i2i belongs to XvX_v for each i∈{1,…,ℓ}i \in\{1,\ldots,\ell\}, and draws edges from vv to all present vertices with a base color not in XvX_v. Note that there are 2ℓ2^\ell possible sets. Then, vv cannot become the “third vertex” of any color (see Figure 5). The problem is whether the base colors φ(v1)\varphi(v_1) and φ(v2)\varphi(v_2) can be validly assigned. The trick is that, as long as the sets XvX_v (v∈Vv \in V) are all distinct, the adversary can always assign valid base colors. Hence, the adversary can maintain the strategy for 2ℓ2^\ell vertices. This yields an Ω(n/log⁡n)\Omega(n/\log n)-competitive lower bound.

References

  1. [1]Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. “The Non-stochastic Multiarmed Bandit Problem”. In: SIAM Journal on Computing 32.1 (2002), pp. 48–77. DOI: 10.1137/S0097539701398375.
  2. [3]Susanne Albers. “Online algorithms: a survey”. In: Mathematical Programming 97.1-2 (2003), pp. 3–26. DOI: 10.1007/s10107-003-0436-0.DOI
  3. [4]Susanne Albers and Sebastian Schraink. “Tight Bounds for Online Coloring of Basic Graph Classes”. In: Algorithmica 83.1 (2021), pp. 337–360. DOI: 10.1007/s00453-020-00759-7.DOI
  4. [5]Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, and Lucia Keller. “Online Coloring of Bipartite Graphs with and without Advice”. In: Algorithmica 70.1 (2014), pp. 92–111. DOI: 10.1007/s00453-013-9819-7.DOI
  5. [6]Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. “k-server via multiscale entropic regularization”. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018). Association for Computing Machinery, 2018, pp. 3–16. DOI: 10.1145/3188745.3188798.DOI
  6. [7]Dwight R. Bean. “Effective coloration”. In: Journal of Symbolic Logic 41.2 (1976), pp. 469–480. DOI: 10.2307/2272247.DOI
  7. [8]Domagoj Bradač, Jacob Fox, Raphael Steiner, Benny Sudakov, and Shengton Zhang. Coloring small locally sparse degenerate graphs and related problems. 2026. arXiv: 2601.15245 [math.CO].arxiv.org/abs/2601.15245
  8. [9]Joakim Blikstad, Ola Svensson, Radu Vintan, and David Wajc. “Online edge coloring is (nearly) as easy as offline”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024). Association for Computing Machinery, 2024, pp. 36–46. DOI: 10.1145/3618260.3649741.DOI
  9. [11]Ekin Ergen. “Online Makespan Scheduling Under Scenarios”. In: 33rd Annual European Symposium on Algorithms (ESA 2025). Vol. 351. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 27:1–27:16. DOI: 10.4230/LIPIcs.ESA.2025.27.DOI
  10. [12]Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. “Competitive paging algorithms”. In: Journal of Algorithms 12.4 (1991), pp. 685–699. DOI: 10.1016/0196-6774(91)90041-V.DOI
  11. [13]Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu. “Lower bounds for on-line graph colorings”. In: Algorithms and Computation (ISAAC 2014). Vol. 8889. Lecture Notes in Computer Science. Springer, 2014, pp. 507–515. DOI: 10.1007/978-3-319-13075-0_40.DOI
  12. [14]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: 10.1002/jgt.3190120212.DOI
  13. [15]Magnús M. Halldórsson. “Online coloring known graphs”. In: The Electronic Journal of Combinatorics 7.1 (2000), R7. DOI: 10.37236/1485.DOI
  14. [16]Magnús M. Halldórsson. “Parallel and On-Line Graph Coloring”. In: Journal of Algorithms 23.2 (1997), pp. 265–280. DOI: 10.1006/jagm.1996.0836.DOI
  15. [17]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.
  16. [18]Sandy Irani. “Coloring inductive graphs on-line”. In: Algorithmica 11.1 (1994), pp. 53–72. DOI: 10.1007/BF01294263.DOI
  17. [19]Hal A. Kierstead. “A polynomial time approximation algorithm for dynamic storage allocation”. In: Discrete Mathematics 88.2-3 (1991), pp. 231–237. DOI: 10.1016/0012-365X(91)90011-P.DOI
  18. [20]Hal A. Kierstead. “Coloring graphs on-line”. In: Online Algorithms: The State of the Art. Ed. by Amos Fiat and Gerhard J. Woeginger. Vol. 1442. Lecture Notes in Computer Science. Springer, 1998, pp. 281–305. DOI: 10.1007/BFb0029574.DOI
  19. [21]Hal A. Kierstead. “On-line coloring k-colorable graphs”. In: Israel Journal of Mathematics 105 (1998), pp. 93–104. DOI: 10.1007/BF02780324.
  20. [22]Hal A. Kierstead and William T. Trotter. “An extremal problem in recursive combinatorics”. In: Congressus Numerantium 33 (1981), pp. 143–153.
  21. [23]Ken-ichi Kawarabayashi, Hirotaka Yoneda, and Masataka Yoneda. “Online Graph Coloring for k-Colorable Graphs”. In: Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). To appear. Society for Industrial and Applied Mathematics, 2027. arXiv: 2511.16100 [cs.DS].arxiv.org/abs/2511.16100
  22. [24]Yaqiao Li. New bounds for online coloring three-colorable graphs. 2026. arXiv: 2610.41516 [cs.DS].arxiv.org/abs/2610.41516
  23. [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. doi: 10.1016/0012-365X(89)90096-4.DOI
  24. [26]Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. “Competitive algorithms for on-line problems”. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988). Association for Computing Machinery, 1988, pp. 322–333. doi: 10.1145/62212.62243.DOI
  25. [27]OpenAI. Squared-logarithmic randomized k-server on arbitrary metrics. OpenAI Math Release preprint. 2026. URL: https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf.
  26. [28]Rajmohan Rajaraman and Omer Wasim. “Competitive Capacitated Online Recoloring”. In: 32nd Annual European Symposium on Algorithms (ESA 2024). Vol. 308. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 95:1–95:17. doi: 10.4230/LIPIcs.ESA.2024.95.
  27. [29]Sundar Vishwanathan. “Randomized Online Graph Coloring”. In: Journal of Algorithms 13.4 (1992), pp. 657–669. doi: 10.1016/0196-6774(92)90061-G.DOI
  28. [30]Hirotaka Yoneda and Masataka Yoneda. “Online Coloring for Graphs of Large Odd Girth”. In: 34th Annual European Symposium on Algorithms (ESA 2026). Vol. 388. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, 127:1–127:15. doi: 10.4230/LIPIcs.ESA.2026.127.DOI

Paper details

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

views · 0

downloads · 0

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

  • Computer Science

GPT-6 Astra

View statement
Looking for related papers…
Contents