k-Coloring Is Now Faster Than Computing the Chromatic Number
k-Coloring is Faster than Computing the Chromatic Number
A new paper by Or Zamir proves that k-coloring on n-vertex graphs can be solved in randomized time (2−ε_k)^n for every fixed k, where ε_k > 0. Previously, only k ≤ 6 had faster algorithms than the general O*(2^n) chromatic number algorithm. The result resolves a long-standing open problem by generalizing and combining tools from a (k+2)-coloring to k-list-coloring reduction and hypergraph containers, plus new algorithms for list-coloring instances with mixed color list lengths.
We prove that k-coloring on n-vertex graphs has a randomized algorithm running in time (2−ε_k)^n, where ε_k > 0 for every fixed k.
- emil-lp
For those not familiar:
K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question.
The chromatic number of a graph is the lowest k for which it has a k-coloring.
Clearly, if you have an algorithm for one, you have an algorithm for the other.
The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number.
Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3.
There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).
- black_knight
At the end of brev paper there is a section on the LLM usage.
Now, this paper will undergo peer review. And thus, when published, we will trust the result as well as any other published result in mathematics. However, while humans are not infallible, LLMs have a tendency to spit out confident stuff which looks correct. Thus I worry when it is used this way to produce proofs. Peer review is not perfect, and may not be tuned to catch LLM’s style of errors.
There is a solution to this, which is to formalise the result and get it machine verified. And with LLMs, I daresay this is going to be best practice moving forward.
- drivebyhooting
Not much faster.
Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.