P453: Enumerate all maximal $k$-colorable subgraphs in a graph

P453: Enumerate all maximal $k$-colorable subgraphs in a graph

Input:

A graph $G = (V, E)$ and an integer $k \ge 4$.

Output:

All maximal $k$-colorable subgraphs in $G$.

Complexity:

$O(2.4023^{|V|})$ total time and $O(2^{|V|})$ space.

Comment:

Reference:

[Byskov2004] (Bibtex)