P451: Enumerate all maximal 3-colorable subgraph of a graph.

P451: Enumerate all maximal 3-colorable subgraph of a graph.

Input:

A graph $G = (V, E)$.

Output:

All maximal 3-colorable subgraphs of $G$.

Complexity:

$O(2.2680^{|V|})$ total time with $O(2^{|V|})$ space.

Comment:

Reference:

[Byskov2004] (Bibtex)