Algorithm colors 3-colorable graphs using fewer colors efficiently
An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs
Data Structures and Algorithms
Summary
Coloring a graph means assigning colors to points so connected points have different colors. When a graph can be colored with three colors, finding such a coloring is very hard. The authors created a faster algorithm that uses fewer colors than previous methods on graphs known to be 3-colorable. They improved the mathematics behind the coloring and combined new and existing methods to reduce the number of colors needed, making the coloring process more efficient.
What this means in practice
- •For graph algorithm engineers: Develop more efficient graph coloring tools for scheduling and resource allocation when exact 3-coloring is impractical.
- •For network designers: Use improved coloring methods to assign frequencies or channels in wireless networks with fewer conflicts when underlying interference graphs are nearly 3-colorable.
A theory result. No direct application yet.
Authors
Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
Abstract
We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $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 $n^{1/6 + o(1)}$-coloring algorithm. Furthermore, we strengthen the SDP-based algorithm specifically for 3-colorable graphs to achieve $O(n^{0.1537})$ colors.