# Fastest way to find optimal graph coloring in polynomial space given chromatic number

Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring.

If such an algorithm isn't known, please tell me so.

This question is not a duplicate, contrary to what the title may suggest: Using the chromatic number to compute an optimal coloring

This is not a homework question, I just want to write a program finding optimal colorings.

• Why do you think knowing the chromatic number helps? How fast is "brute-force"? Jan 6, 2022 at 20:01
• @PålGD Regarding your first question, I don't know (except in the brute force case). I arrived at this question because after looking up a few fast exponential algorithms for "coloring" I realized that they all actually compute the chromatic number, and it's not obvious to me whether it's possible to reconstruct the optimal coloring from their data structures after the chromatic number is found. Jan 6, 2022 at 20:46
• @PålGD Regarding the second question, I think there are two possible brute-force approaches, I think that one is O(n!*n) (greedy coloring on all possible node orderings), the other one is O(k^n). Here n is the number of nodes and k is the number of colors. Jan 6, 2022 at 20:48
• There is actually a $2.461^n$ algorithm to compute the chromatic number of a graph using polynomial space. Jan 6, 2022 at 21:15
• No, you have an oracle that runs in $2.461^n$ time and polynomial space. Can you use that to get the colouring in the same time? Check again the answer by Y Filmus. Jan 7, 2022 at 8:35