Graph / Coloring (Bibtex)

P122: Enumeration of all the edge colorings in a bipartite graph

Input:

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

Output:

All edge colorings in $G$.

Complexity:

$O(\Delta|E|)$ time per solution and space.

Comment:

$\Delta$ is the maximum degree in $G$.

Reference:

[Yasuko1994] (Bibtex)

P86: Enumeration of all the edge colorings of a bipartite graph

Input:

A bipartite graph $B = (V, E)$.

Output:

All the edge colorings pf $B$.

Complexity:

$O(T(|V|+|E|+\Delta) + K \min \{|V|^2 + |E|, T(|V|, |E|, \Delta)\})$ total time and $O(|E|\Delta)$ space.

Comment:

$\Delta$ is the number of maximum degree and $T(|V|, |E|, \Delta)$ is the time complexity of an edge coloring algorithm.

Reference:

[Matsui1996b] (Bibtex)

P87: Enumeration of all the edge colorings of a bipartite graph

Input:

A bipartite graph $B = (V, E)$.

Output:

All the edge colorings pf $B$.

Complexity:

$O(|V|)$ time per solution and $O(|E|)$ space.

Comment:

Reference:

[Matsui1996a] (Bibtex)

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)

P452: Enumerate all maximal 6-colorable subgraph in a graph.

Input:

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

Output:

All maximal 6-colorable subgraphs in $G$.

Complexity:

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

Comment:

Reference:

[Byskov2004] (Bibtex)

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)