color(3_colorable_graph);

Posted: Dec 19th 2024
Abstract

🎨 Coloring a 3-colorable graph.

color(3_colorable_graph);

A Little Background Story

In the Fall 2024 semester, I took an advanced graph algorithm course at University of Illinois Urbana-Champaign just for fun. The space here is too little, so I'll ask you to move to my note to get a better idea of the course. Here, I want to share something more specific: the final project I and Sean Liu worked on, which is basically a literature review of a cute line of work about graph coloring.

Coloring a 3-Colorable Graph

Given an undirected 333-colorable graph G=(V,E)G = (V, E)G=(V,E), we would like to color GGG with the least number of colors efficiently. Recently, Professor Kawarabayashi, who I know during my intern at NII, worked on this problem extensively and got several exciting results on this problem, where they are able to break the natural barrier of O~(n0.2)\widetilde{O} (n^{0.2})O(n0.2) colors down to O~(n0.19747)\widetilde{O} (n^{0.19747})O(n0.19747) colors [KTY24]. This problem was first proposed by Wigderson [Wig83], and we shall see how balancing combinatorial with semi-definite programming (SDP) methods leads to a natural O(n0.5)O(n^{0.5})O(n0.5) bound, and how this was first broken [KT17]. We focus on the combinatorial side, specifically Blum's contributions [Blu94] that laid the groundwork for most of Kawarabayashi etal.'s later breakthroughs [KT12,KT17,KTY24].

General Strategy

One of the most important notions in this line of work originates from Blum's progress towards kkk-coloring [Blu94]. While deferring the exact definition, the general idea is that if it is always possible to make progress (towards some fixed kkk) for any 333-colorable graph, then we can O~(k)\widetilde{O}(k)O(k)-color any 333-colorable graph in polynomial time. An interesting aspect of this line of work is that, under different regimes, two different approaches dominate one another. The best bound is obtained by balancing between them via choosing an appropriate Δ\DeltaΔ: specifically, for any parameter Δ\DeltaΔ, it suffices to make progress under either a minimum degree Δ=Δmin⁡\Delta = \Delta_{\min }Δ=Δmin​ or maximum degree Δ=Δmax⁡\Delta = \Delta_{\max}Δ=Δmax​ constraint [AC06,BK97,KT17].

Known Results

Assuming that for a 333-colorable graph with minimum degree Δmin⁡=n1−Ω(1)\Delta_{\min} = n^{1 - \Omega(1)}Δmin​=n1−Ω(1), a series of bounds from past literature for progress follows a sequence of the form:

\widetilde{O}\left(\left(n/\Delta_{\min}\right)^{i/(2i-1)}\right),

including O~(n/Δmin⁡)\widetilde{O}(n/\Delta_{\min})O(n/Δmin​) by Wigderson [Wig83] for i=1i=1i=1, O~((n/Δmin⁡)2/3)\widetilde{O}((n/\Delta_{\min})^{2/3})O((n/Δmin​)2/3) and O~((n/Δmin⁡)3/5)\widetilde{O}((n/\Delta_{\min})^{3/5})O((n/Δmin​)3/5) for i=2i = 2i=2 and 333 by Blum [Blu94], and finally O~((n/Δmin⁡)4/7)\widetilde{O}((n/\Delta_{\min})^{4/7})O((n/Δmin​)4/7) for i=4i = 4i=4 by Kawarabayashi and Thorup [KT12].

Combinatorial Bounds for High Minimum Degree

The first series of bounds implied by the general bound stems from the simple observation that we may assume the minimum degree Δmin⁡≥k\Delta_{\min} \geq kΔmin​≥k given any targeted coloring number. This is because it is trivial to color the rest of the graph after coloring vertices with a degree exceeding kkk. Hence, from the general bound for i=[4]i = [4]i=[4], Δmin⁡≥k=(n/Δmin⁡)i/(2i−1)  ⟺  Δmin⁡≥ni/(3i−1)\Delta_{\min} \geq k = (n/\Delta_{\min})^{i / (2i-1)} \iff \Delta_{\min} \geq n^{i / (3i-1)}Δmin​≥k=(n/Δmin​)i/(2i−1)⟺Δmin​≥ni/(3i−1), which yields an O~(ni/(3i−1))\widetilde{O}(n^{i/(3i-1)})O(ni/(3i−1)) bound for any Δmin⁡≥ni/(3i−1)\Delta_{\min} \geq n^{i/(3i-1)}Δmin​≥ni/(3i−1). Thus, we get O~(n1/2)\widetilde{O}(n^{1/2})O(n1/2) for i=1i=1i=1 [Wig83], O~(n2/5)\widetilde{O}(n^{2/5})O(n2/5) and O~(n3/8)\widetilde{O}(n^{3/8})O(n3/8) for i=2i=2i=2 and 333, respectively [Blu94], and O~(n4/11)\widetilde{O}(n^{4/11})O(n4/11) for i=4i=4i=4 [KT12].

SDP Bounds for Low Maximum Degree

For 333-colorable graphs with maximum degree Δmax⁡\Delta_{\max}Δmax​, Karger etal. [KMS98] used SDP to achieve O(Δmax⁡1/3)O(\Delta_{\max}^{1/3})O(Δmax1/3​) colors. Combining with the general bound, one can color 333-colorable graphs with O~(ni/(5i−1))\widetilde{O}(n^{i/(5i-1)})O(ni/(5i−1)) colors for i∈[4]i \in [4]i∈[4] by balancing Δmax⁡1/3\Delta_{\max}^{1/3}Δmax1/3​ and (n/Δmin⁡)i/(2i−1)(n/\Delta_{\min})^{i/(2i-1)}(n/Δmin​)i/(2i−1) [BK97]. In particular, the following general lemma for balancing is known:

Lemma (Balancing [KT17]). Suppose for some near-polynomial ddd and fff that for any nnn, we can make progress towards an O~(f(n))\widetilde{O}(f(n))O(f(n)) coloring for any 333-colorable graph with either Δmin⁡≥d(n)\Delta_{\min} \geq d(n)Δmin​≥d(n); or Δmax⁡≤d(n)\Delta_{\max} \leq d(n)Δmax​≤d(n), then we can make progress towards O~(f(n))\widetilde{O}(f(n))O(f(n))-coloring on any 333-colorable graph.

This gives O~(n1/4)\widetilde{O}(n^{1/4})O(n1/4) for i=1i=1i=1 and O~(n3/14)=O~(n0.2142)\widetilde{O}(n^{3/14}) = \widetilde{O}(n^{0.2142})O(n3/14)=O(n0.2142) for i=3i = 3i=3. We omit i=4i=4i=4 [KT12] as this appears much later, and further improvements on the SDP bounds have already been achieved. As the general bound converges to O~((n/Δmin⁡)1/2)\widetilde{O}((n/\Delta_{\min})^{1/2})O((n/Δmin​)1/2) from above, the bound O~(n1/5)\widetilde{O}(n^{1/5})O(n1/5) emerges as a natural barrier. Later improvements in SDP combined with Blum's result [Blu94] suggest a similar barrier: Arora etal. [AC06] achieved O(n0.2111)O(n^{0.2111})O(n0.2111) colors based on the sparsest cut SDP [ARV09], while Chlamtac [Chl07] further improved it to O(n0.2072)O(n^{0.2072})O(n0.2072). Both results rely on bounds of the form O(Δmax⁡1/3−ε(n,Δmax⁡))O(\Delta_{\max}^{1/3 - \varepsilon(n, \Delta_{\max})})O(Δmax1/3−ε(n,Δmax​)​), where ε(n,Δ)>0\varepsilon(n, \Delta) > 0ε(n,Δ)>0 is a small value that decreases as a complex function of Δ\DeltaΔ. With these new SDP results, the combinatorial bound O~(n4/11)\widetilde{O}(n^{4/11})O(n4/11) for i=4i=4i=4 yields a final bound of O~(n0.2049)\widetilde{O}(n^{0.2049})O(n0.2049) colors [KT12].

Balancing

A more careful treatment of balancing different regimes finally leads to a breakthrough: while the general bound converges to O~((n/Δmin⁡)1/2)\widetilde{O}((n/\Delta_{\min})^{1/2})O((n/Δmin​)1/2) from above with the natural condition Δmin⁡≥n1/3\Delta_{\min} \geq n^{1/3}Δmin​≥n1/3, if our goal is to balance it with the SDP bounds such as Δmax⁡1/3\Delta_{\max}^{1/3}Δmax1/3​, the general bound only needs to hold when Δmin⁡≥n3/5\Delta_{\min} \geq n^{3/5}Δmin​≥n3/5. This idea is exploited in [KT17] to show that the general bound holds for i=12i=12i=12 when Δmin⁡≥n0.61674333\Delta_{\min} \geq n^{0.61674333}Δmin​≥n0.61674333. Combining the best current SDP bound [Chl07], this yields an overall coloring bound of O~(n0.19996)\widetilde{O}(n^{0.19996})O(n0.19996), breaking the O~(n1/5)\widetilde{O}(n^{1/5})O(n1/5) barrier. The latest advancement [KTY24] further improves the combinatorial bound, where the limit of the general bound, i.e., O~((n/Δ)1/2)\widetilde{O}((n/\Delta)^{1/2})O((n/Δ)1/2), can be approached arbitrarily when Δmin⁡>n\Delta_{\min} > \sqrt{n}Δmin​>n​:

Theorem ([KTY24]). For any 333-colorable graph with Δmin⁡>n0.5\Delta_{\min} > n^{0.5}Δmin​>n0.5, we can make progress towards a kkk-coloring for some k=2(log⁡log⁡n)2n/Δmin⁡k = 2^{(\log \log n)^2} \sqrt{n/\Delta_{\min}}k=2(loglogn)2n/Δmin​​ in polynomial time.

Combining the above theorem with the best SDP bound [Chl07] at Δmin⁡=n0.605073\Delta_{\min} = n^{0.605073}Δmin​=n0.605073, an O~(n0.19747)\widetilde{O}(n^{0.19747})O(n0.19747)-coloring can also be found in polynomial time.

Conclusion

In this blog post, we review the literature and try to grasp the high level idea of the history of the problem and how the breakthrough is made. The complete and detailed report is available.

Last Updated on Jun 21st 2025