Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring)

Time Complexity

$O({1.7272}^n)$

Space Complexity

$O(n)$ words

(Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

2007

Reference

https://link-springer-com.ezproxy.canberra.edu.au/chapter/10.1007/978-3-540-73545-8_9