betaFeedback

WorksComputer Science

An O(n0.1537)O(n^{0.1537})-Coloring Algorithm for 3-Colorable Graphs

Abstract

We present a polynomial-time randomized algorithm that colors every nn-vertex 33-colorable graph with O(n0.1537)O(n^{0.1537}) colors. This improves upon the previous bound of O(n0.1954)O(n^{0.1954}) colors by Bansal, Huang, and Lee (SODA '27). To achieve this result, we introduce a new algorithmic framework for finding a large independent set from a solution to the vector coloring SDP. Combined with the (combinatorial) dense-progress algorithm of Kawarabayashi, Thorup, and Yoneda (STOC '24), this framework yields an n1/6+o(1)n^{1/6 + o(1)}-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve O(n0.1537)O(n^{0.1537}) colors.

Introduction

The question of graph coloring, which colors each vertex of a given graph G=(V,E)G=(V,E) with the smallest number of colors so that adjacent vertices always have different colors, is a central topic in both discrete math and theoretical computer science. This is not only one of the most important NP-hard problems, but even deciding whether three colors suffice is among Karp’s 21 classic NP-complete problems [23, 34].

Indeed, the fastest known algorithm to solve graph coloring takes O∗(2n)O^*(2^n) time [6], where nn is the number of vertices. For determining whether the graph is kk-colorable, the fastest known algorithm takes O∗(1.3289n)O^*(1.3289^n) time for k=3k=3 [4], O∗(1.7159n)O^*(1.7159^n) time for k=4k=4 [49], and O∗((2−εk)n)O^*((2-\varepsilon_k)^n) time for k=5,6k=5,6 for some very small εk>0\varepsilon_k>0 [51]. Very recently, two independent preprints that claim O∗((2−εk)n)O^*((2-\varepsilon_k)^n) time for all k∈Nk\in\mathbb{N} appeared [Zam26; Pra26]. Polynomial-time algorithms are known only for limited graph classes, including perfect graphs [26] and bounded-treewidth graphs [CFK+15].

Approximation Algorithms

Approximation algorithms are well studied for NP-hard problems in general. However, graph coloring is NP-hard even to approximate within an n1−εn^{1-\varepsilon} factor for all ε>0\varepsilon>0 [20, 31, 53]. Note that the best known approximation factor is O(n(log⁡log⁡n)2/(log⁡n)3)O(n(\log\log n)^2/(\log n)^3) [13, 30].

Given very strong negative results for the approximation, the following question became the main line of research: “Given a kk-colorable graph G=(V,E)G=(V,E), find a coloring in polynomial time, using a sufficiently small number of colors.” In particular, the case k=3k=3 is important for being the smallest nontrivial case, and improving this case typically yields a better algorithm for all subsequent k≥4k\geq4 [12, 32].

This topic also connects deeply to a central problem in complexity theory, the Unique Games Conjecture, and its variant, the d-to-1 Conjecture, both introduced by Khot [35]. If the d-to-1 Conjecture is true for some constant dd, then it is NP-hard to color 3-colorable graphs with any constant number of colors in polynomial time [18, 28]. Very recently, a preprint that claims to resolve the 4-to-1 Conjecture appeared [FMW26], which, if true, would resolve the impossibility for any constant number of colors. Meanwhile, unconditional NP-hardness was already known for coloring kk-colorable graphs with 2k−12k-1 colors [36, 24, 9].

Polynomial-Time Coloring of 3-Colorable Graphs

Wigderson [50] initiated research on coloring 3-colorable graphs in 1982, presenting an O(n)O(\sqrt{n})-coloring algorithm. Since then, researchers have made a long line of improvements over 40 years, approaching the problem from two sides: the large-degree case and the small-degree case. We present the sequence of improvements in Table 1.

Two directions of the attack. Generally speaking, if we want to create an algorithm to color 3-colorable graphs with O~(nα)\widetilde{O}(n^\alpha) colors (for α∈(0,1)\alpha\in(0,1)), we consider an algorithm to make “progress” toward O~(nα)\widetilde{O}(n^\alpha)-coloring. Here, the progress includes obtaining an independent set of size Ω~(n1−α)\widetilde{\Omega}(n^{1-\alpha}), as repeating the routine of “coloring the independent set with a common new color and removing these vertices from the graph” until the graph becomes empty gives an O~(nα)\widetilde{O}(n^\alpha)-coloring. Note that, while Blum [12] also considers other types of progress,5 which are used in solving the large-degree case including [42], we do not take them into account in this paper.

YearPaperColorsResult Description (Informal)
1982[50]O~(n1/2)\widetilde{O}(n^{1/2})Combinatorial. The first nontrivial algorithm for coloring 3-colorable graphs.
1989[Blu89]O~(n2/5)\widetilde{O}(n^{2/5})Combinatorial. Utilized the second neighborhood with a (2−log⁡log⁡nlog⁡n)(2-\frac{\log\log n}{\log n})-approximation algorithm for vertex cover [5].
1990[11]O~(n3/8)\widetilde{O}(n^{3/8})Combinatorial. Improved the case where the structure between the first and second neighborhoods is dense.
1994[37]O~(n1/4)\widetilde{O}(n^{1/4})SDP. Applied semidefinite programming (SDP) to the problem and achieved O~(Δ1/3)\widetilde{O}(\Delta^{1/3}) colors for maximum degree Δ\Delta.
1997[BK97]O~(n3/14)\widetilde{O}(n^{3/14})Devised a framework that combines small-degree and large-degree progress.
2006[1]O~(n0.2111)\widetilde{O}(n^{0.2111})SDP. Devised a better rounding scheme that considers the second neighborhood.
2007[17]O~(n0.2072)\widetilde{O}(n^{0.2072})SDP. Considered a higher-degree SDP using Lasserre’s sum-of-squares hierarchy [43].
2012[39]O~(n0.2049)\widetilde{O}(n^{0.2049})Combinatorial. Introduced the idea of “sparse cut”; the best known purely combinatorial solution with O~(n4/11)\widetilde{O}(n^{4/11}) colors.
2014[40]O~(n0.2000)\widetilde{O}(n^{0.2000})Combinatorial. Introduced a new recursive subroutine that makes progress with even smaller dense substructures.
2024[42]O~(n0.1975)\widetilde{O}(n^{0.1975})Combinatorial. Introduced the idea of “side cut”, and finally completed a framework toward (n/Δ)1/2no(1)(n/\Delta)^{1/2}n^{o(1)}-coloring for degree Δ\Delta.
2026[7]O~(n0.1954)\widetilde{O}(n^{0.1954})SDP. Considered the third neighborhood structure and combined it with a new “vector 52\frac{5}{2}-coloring” idea.
2026OursO(n0.1537)O(n^{0.1537})SDP. Introduced iterative local-maximum selection under Gaussian projections with Gaussian cover lifting.

Table 1. Table 1: The line of research for coloring 3-colorable graphs in polynomial time. Although not listed below, some very recent preprints claim the following results: O~(n0.1751)\widetilde{O}(n^{0.1751}) colors on September 27, 2026 [46], O~(n0.1780)\widetilde{O}(n^{0.1780}) colors on September 30, 2026 [45], O~(n0.1740)\widetilde{O}(n^{0.1740}) colors on October 1, 2026 [3], and O~(n0.1653)\widetilde{O}(n^{0.1653}) colors on October 2, 2026 [48].

The following framework is widely used: for an arbitrary threshold Δ\Delta, it suffices to consider making progress toward O~(nα)\widetilde{O}(n^\alpha)-coloring for graphs with maximum degree ≤Δ\le\Delta and for graphs with minimum degree ≥Δ\ge\Delta ([41], Proposition 7.1). For this reason, an improvement on either the large-degree case or the small-degree case yields a better algorithm for 3-colorable graphs.

The starting point: Wigderson’s algorithm. For graphs with minimum degree Δ\Delta, the induced subgraph G[N(x)]G[N(x)] on the neighborhood of x∈Vx \in V is bipartite, with at least Δ\Delta vertices. Hence, an independent set of size ≥Δ/2\ge\Delta/2 can be obtained in linear time (by bipartite coloring), making progress toward O(n/Δ)O(n/\Delta)-coloring. Graphs with maximum degree Δ\Delta can be colored with Δ+1\Delta+ 1 colors by greedy coloring. Wigderson combined them with threshold Δ=n\Delta= \sqrt{n} and yielded an O(n)O(\sqrt{n})-coloring algorithm.

Large-degree case and combinatorics. In 1989, Blum achieved the first improvement over Wigderson’s algorithm; his line of work [Blu89; Blu90; Blu94] yields a better algorithm for the large-degree cases, which makes progress toward O~((n/Δ)3/5)\widetilde{O}((n/\Delta)^{3/5})-coloring. The attack on the large-degree case is mainly done in a combinatorial way, analyzing dense substructures of a graph. The best known algorithm for the large-degree case makes progress toward (n/Δ)1/2no(1)(n/\Delta)^{1/2}n^{o(1)}-coloring for every fixed ε>0\varepsilon> 0, whenever the minimum degree Δ>n\Delta> \sqrt{n} [42]. Therefore, we can use the following tool when combined with the small-degree case.

Theorem 1 ([42], restated). Fix α∈(0,14]\alpha\in(0, \frac{1}{4}]. Suppose that there exists an algorithm that, given a 3-colorable graph with maximum degree Δ<n1−2α\Delta< n^{1-2\alpha}, obtains an independent set of size n1−α−o(1)n^{1-\alpha-o(1)} in polynomial time. Then, one can color a 3-colorable graph with nα+o(1)n^{\alpha+o(1)} colors in polynomial time.

Small-degree case and SDP. On the other hand, improvements on the small-degree case generally involve semidefinite programming (SDP). Goemans and Williamson’s 1994 landmark result, which achieves a 0.878-approximation of the maximum cut problem via SDP [29], sparked interest in applying SDP to other optimization problems. In the same year, Karger, Motwani, and Sudan [37, 38] presented an SDP-based algorithm that, given a 3-colorable graph with maximum degree Δ\Delta, computes an O~(Δ1/3)\widetilde{O}(\Delta^{1/3})-coloring in polynomial time. Their SDP formulation is “vector kk-coloring”, defined to be vectors {vx}x∈V\{v_x\}_{x\in V} in Rn\mathbb{R}^n such that ∥vx∥=1\lVert v_x\rVert= 1 for all x∈Vx \in V and ⟨vx,vy⟩≤−1k−1\langle v_x, v_y\rangle\le-\frac{1}{k-1} for all xy∈Exy \in E. It is not hard to see that if the graph is kk-colorable, then a vector kk-coloring exists and can be computed in polynomial time via a polynomial-time SDP algorithm [25]. A rounding scheme on vector 3-coloring enabled them to obtain an independent set of size Ω~(n/Δ1/3)\widetilde{\Omega}(n/\Delta^{1/3}) with high probability.

Combining this with [42]’s framework (Theorem 1) gives n1/5+o(1)n^{1/5+o(1)} colors, splitting at Δ=n3/5\Delta= n^{3/5}. As further studies on the SDP side [1, 17, 7] improve the bounds when Δ\Delta is large, the best known algorithm [7] achieves an exponent slightly better than 15\frac{1}{5}.

Related works. Some studies consider coloring 3-colorable graphs with a specific structure. Alon and Kahale [2] showed, using spectral graph theory, a polynomial-time algorithm to find a 3-coloring for random 3-colorable graphs. Recently, Hsieh [33] presented a polynomial-time algorithm to find a large independent set for 3-colorable graphs with low threshold rank.

Our Results

In this paper, we make an improvement to the small-degree cases for the problem of coloring 3-colorable graphs in polynomial time. Specifically, we obtain the following results.

Theorem 2. Fix a real number k>2k > 2 and β∈(0,1]\beta\in(0,1]. Let G=(V,E)G = (V,E) be a graph on nn vertices with maximum degree at most nβn^\beta, given together with an ordinary vector kk-coloring, that is, unit vectors {vx}x∈V\{v_x\}_{x\in V} with

⟨vx,vy⟩≤−1k−1\langle v_x,v_y\rangle\le-\frac{1}{k-1} for every edge xy∈Exy \in E. For every fixed C>0C > 0, there is a randomized polynomial-time algorithm that, with probability at least 1−n−C1-n^{-C}, returns an independent set II with

References

  1. [1]Sanjeev Arora, Eden Chlamtáč, and Moses Charikar. “New approximation guarantee for chromatic number”. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006). Association for Computing Machinery, 2006, pp. 215–224. DOI: 10.1145/1132516.1132548.DOI
  2. [2]Noga Alon and Nabil Kahale. “A Spectral Technique for Coloring Random 3-Colorable Graphs”. In: SIAM Journal on Computing 26.6 (1997), pp. 1733–1748. DOI: 10.1137/S0097539794270248.DOI
  3. [3]Emile Anand. Coloring 3-Colorable Graphs with O(n⁴⁄²³) Colors via a Gaussian-Cover Recursion. 2026. arXiv: 2610.01071 [cs.DS]. URL: https://arxiv.org/abs/2610.01071.
  4. [4]Richard Beigel and David Eppstein. “3-coloring in time O(1.3289ⁿ)”. In: Journal of Algorithms 54.2 (2005), pp. 168–204. doi: 10.1016/j.jalgor.2004.06.008.DOI
  5. [5]Reuven Bar-Yehuda and Shimon Even. “A local-ratio theorem for approximating the weighted vertex cover problem”. In: Analysis and Design of Algorithms for Combinatorial Problems. Ed. by G. Ausiello and M. Lucertini. Vol. 25. Annals of Discrete Mathematics. North-Holland, 1985, pp. 27–45. doi: 10.1016/S0304-0208(08)73101-3.
  6. [6]Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. “Set partitioning via inclusion-exclusion”. In: SIAM Journal on Computing 39.2 (2009), pp. 546–563. DOI: 10.1137/070683933.DOI
  7. [7]Nikhil Bansal, Neng Huang, and Euiwoong Lee. “Improved SDP-Based Algorithm for Coloring 3-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: 2602.05904 [cs.DS]. URL: https://arxiv.org/abs/2602.05904.
  8. [9]Jakub Bulín, Andrei Krokhin, and Jakub Opršal. “Algebraic approach to promise constraint satisfaction”. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). Association for Computing Machinery, 2019, pp. 602–613. DOI: 10.1145/3313276.3316300.DOI
  9. [11]Avrim Blum. “Some tools for approximate 3-coloring”. In: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS 1990). IEEE, 1990, pp. 554–562. DOI: 10.1109/FSCS.1990.89576.
  10. [12]Avrim Blum. “New approximation algorithms for graph coloring”. In: Journal of the ACM 41.3 (1994), pp. 470–516. DOI: 10.1145/176584.176586.DOI
  11. [13]Bonnie Berger and John Rompel. “A better performance guarantee for approximate graph coloring”. In: Algorithmica 5 (1990), pp. 459–466. DOI: 10.1007/BF01840398.DOI
  12. [14]Wei-Kuo Chen, Nikos Dafnis, and Grigoris Paouris. “Improved Hölder and Reverse Hölder Inequalities for Gaussian Random Vectors”. In: Advances in Mathematics 280 (2015), pp. 643–689. DOI: 10.1016/j.aim.2014.09.029.DOI
  13. [16]Eden Chlamtáč and Ishay Haviv. “Linear Index Coding via Semidefinite Programming”. In: Combinatorics, Probability and Computing 23.2 (2014), pp. 223–247. DOI: 10.1017/S0963548313000564.DOI
  14. [17]Eden Chlamtáč. “Approximation algorithms using hierarchies of semidefinite programming relaxations”. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007). IEEE, 2007, pp. 691–701. DOI: 10.1109/FOCS.2007.4389537.DOI
  15. [18]Irit Dinur, Elchanan Mossel, and Oded Regev. “Conditional Hardness for Approximate Coloring”. In: SIAM Journal on Computing 39.3 (2009), pp. 843–873. DOI: 10.1137/07068062X.DOI
  16. [19]Antoine Ehrhard. “Symétrisation dans l’espace de Gauss”. In: Mathematica Scandinavica 53 (1983), pp. 281–301. DOI: 10.7146/math.scand.a-12035.DOI
  17. [20]Uriel Feige and Joe Kilian. “Zero Knowledge and the Chromatic Number”. In: Journal of Computer and System Sciences 57.2 (1998), pp. 187–199. DOI: 10.1006/jcss.1998.1587.DOI
  18. [21]Uriel Feige, Michael Langberg, and Gideon Schechtman. “Graphs with tiny vector chromatic numbers and huge chromatic numbers”. In: SIAM Journal on Computing 33.6 (2004), pp. 1338–1368. DOI: 10.1137/S0097539703431391.DOI
  19. [23]Michael R. Garey, David S. Johnson, and Larry Stockmeyer. “Some Simplified NP-Complete Problems”. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing (STOC 1974). Association for Computing Machinery, 1974, pp. 47–63. DOI: 10.1145/800119.803884.DOI
  20. [24]Venkatesan Guruswami and Sanjeev Khanna. “On the hardness of 4-coloring a 3-colorable graph”. In: SIAM Journal on Discrete Mathematics 18.1 (2004), pp. 30–40. DOI: 10.1137/S0895480100376794.DOI
  21. [25]Martin Grötschel, László Lovász, and Alexander Schrijver. “The ellipsoid method and its consequences in combinatorial optimization”. In: Combinatorica 1.2 (1981), pp. 169–197. DOI: 10.1007/BF02579273.DOI
  22. [26]Martin Grötschel, László Lovász, and Alexander Schrijver. “Polynomial algorithms for perfect graphs”. In: Topics on Perfect Graphs. Ed. by Claude Berge and Václav Chvátal. Vol. 21. Annals of Discrete Mathematics. North-Holland, 1984, pp. 325–356. DOI: 10.1016/S0304-0208(08)72943-8.DOI
  23. [27]Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Vol. 2. Algorithms and Combinatorics. Springer, 1988. doi: 10.1007/978-3-642-97881-4.DOI
  24. [28]Venkatesan Guruswami and Sai Sandeep. “d-to-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors”. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Vol. 168. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, 62:1–62:12. doi: 10.4230/LIPIcs.ICALP.2020.62.DOI
  25. [29]Michel X. Goemans and David P. Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. In: Journal of the ACM 42.6 (1995), pp. 1115–1145. doi: 10.1145/227683.227684.DOI
  26. [30]Magnús M. Halldórsson. “A still better performance guarantee for approximate graph coloring”. In: Information Processing Letters 45.1 (1993), pp. 19–23. doi: 10.1016/0020-0190(93)90246-6.DOI
  27. [31]Johan Håstad. “Clique Is Hard to Approximate within n^{1−ε}”. In: Acta Mathematica 182.1 (1999), pp. 105–142. doi: 10.1007/BF02392825.DOI
  28. [32]Eran Halperin, Ram Nathaniel, and Uri Zwick. “Coloring k-colorable graphs using relatively small palettes”. In: Journal of Algorithms 45.1 (2002), pp. 72–90. doi: 10.1016/S0196-6774(02)00217-1.DOI
  29. [33]Jun-Ting Hsieh. “Coloring 3-colorable graphs with low threshold rank”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2026, pp. 718–726. doi: 10.1137/1.9781611978971.27.DOI
  30. [34]Richard M. Karp. “Reducibility among combinatorial problems”. In: Complexity of Computer Computations. Ed. by Raymond E. Miller and James W. Thatcher. Plenum Press, 1972, pp. 85–103. doi: 10.1007/978-1-4684-2001-2_9.DOI
  31. [35]Subhash Khot. “On the power of unique 2-prover 1-round games”. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002). Association for Computing Machinery, 2002, pp. 767–775. doi: 10.1145/509907.510017.DOI
  32. [36]Sanjeev Khanna, Nathan Linial, and Shmuel Safra. “On the hardness of approximating the chromatic number”. In: Combinatorica 20.3 (2000), pp. 393–415. doi: 10.1007/s004930070013.DOI
  33. [37]David Karger, Rajeev Motwani, and Madhu Sudan. “Approximate Graph Coloring by Semidefinite Programming”. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1994). IEEE, 1994, pp. 2–13. doi: 10.1109/SFCS.1994.365710.
  34. [38]David Karger, Rajeev Motwani, and Madhu Sudan. “Approximate graph coloring by semidefinite programming”. In: Journal of the ACM 45.2 (1998), pp. 246–265. doi: 10.1145/274787.274791.DOI
  35. [39]Ken-ichi Kawarabayashi and Mikkel Thorup. “Combinatorial coloring of 3-colorable graphs”. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012). IEEE, 2012, pp. 68–75. doi: 10.1109/FOCS.2012.16.DOI
  36. [40]Ken-ichi Kawarabayashi and Mikkel Thorup. “Coloring 3-colorable graphs with \(o(n^{1/5})\) colors”. In: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Vol. 25. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014, pp. 458–469. doi: 10.4230/LIPIcs.STACS.2014.458.DOI
  37. [41]Ken-ichi Kawarabayashi and Mikkel Thorup. “Coloring 3-Colorable Graphs with Less than \(n^{1/5}\) Colors”. In: Journal of the ACM 64.1 (2017), 4:1–4:23. Doi: 10.1145/3001582.DOI
  38. [42]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). Association for Computing Machinery, 2024, pp. 331–339. doi: 10.1145/3618260.3649768.DOI
  39. [43]Jean B. Lasserre. “An explicit exact SDP relaxation for nonlinear 0-1 programs”. In: Integer Programming and Combinatorial Optimization (IPCO 2001). Vol. 2081. Lecture Notes in Computer Science. Springer, 2001, pp. 293–303. doi: 10.1007/3-540-45535-3_23.DOI
  40. [44]László Lovász. “On the Shannon Capacity of a Graph”. In: IEEE Transactions on Information Theory 25.1 (1979), pp. 1–7. doi: 10.1109/TIT.1979.1055985.DOI
  41. [45]Konstantin Makarychev and Yury Makarychev. Sharper Gaussian Covers in the Bansal–Huang–Lee Coloring Framework. 2026. arXiv: 2609.40136 [cs.DS]. URL: https://arxiv.org/abs/2609.40136.
  42. [46]Ijay Narang and Yukai Tang. Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates. 2026. arXiv: 2609.33684 [cs.DS]. URL: https://arxiv.org/abs/2609.33684.
  43. [48]Zhao Song. An \(O(n^{1/6})\)-coloring algorithm for 3-colorable graphs. SSRN preprint 7551399. 2026. Doi: 10.2139/ssrn.7551399. URL: https://ssrn.com/abstract=7551399.DOI
  44. [49]Pu Wu, Huanyu Gu, Huiqin Jiang, Zehui Shao, and Jin Xu. “A faster algorithm for the 4-coloring problem”. 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, 103:1–103:18. doi: 10.4230/LIPIcs.ESA.2024.103.DOI
  45. [50]Avi Wigderson. “A new approximate graph coloring algorithm”. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC 1982). Association for Computing Machinery, 1982, pp. 325–329. doi: 10.1145/800070.802207.DOI
  46. [51]Or Zamir. “Breaking the 2ⁿ barrier for 5-coloring and 6-coloring”. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Vol. 198. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 113:1–113:20. doi: 10.4230/LIPIcs.ICALP.2021.113.DOI
  47. [53]David Zuckerman. “Linear degree extractors and the inapproximability of max clique and chromatic number”. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006). Association for Computing Machinery, 2006, pp. 681–690. DOI: 10.1145/1132516.1132612.DOI

Paper details

vlnc:W_xpxgw7a8
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, GPT-6 Pro, GPT-5.6 Sol (bare), GPT-6 Sol, Claude Opus 5.5

View statement
Looking for related papers…
Contents