The Algorithm Design Manual Second Edition

5.7.2

Two-Coloring Graphs

The vertex-coloring problem seeks to assign a label (or color) to each vertex of a

graph such that no edge links any two vertices of the same color. We can easily

avoid all conflicts by assigning each vertex a unique color. However, the goal is to

use as few colors as possible. Vertex coloring problems often arise in scheduling

applications, such as register allocation in compilers. See Section

16.7

(page

544

)

for a full treatment of vertex-coloring algorithms and applications.

---

168

5 .

G R A P H T R A V E R S A L

A graph is bipartite if it can be colored without conflicts while using only two

colors. Bipartite graphs are important because they arise naturally in many appli-

cations. Consider the “had-sex-with” graph in a heterosexual world. Men have sex

only with women, and vice versa. Thus, gender defines a legal two-coloring, in this

simple model.

But how can we find an appropriate two-coloring of a graph, thus separating

the men from the women? Suppose we assume that the starting vertex is male.

All vertices adjacent to this man must be female, assuming the graph is indeed

bipartite.

We can augment breadth-first search so that whenever we discover a new vertex,

we color it the opposite of its parent. We check whether any nondiscovery edge links

two vertices of the same color. Such a conflict means that the graph cannot be two-

colored. Otherwise, we will have constructed a proper two-coloring whenever we

terminate without conflict.

twocolor(graph *g)

{

int i;

/* counter */

for (i=1; i<=(g->nvertices); i++)

color[i] = UNCOLORED;

bipartite = TRUE;

initialize_search(&g);

for (i=1; i<=(g->nvertices); i++)

if (discovered[i] == FALSE) {

color[i] = WHITE;

bfs(g,i);

}

}

process_edge(int x, int y)

{

if (color[x] == color[y]) {

bipartite = FALSE;

printf("Warning: not bipartite due to (%d,%d)\n",x,y);

}

color[y] = complement(color[x]);

}

---

5 . 8

D E P T H - F I R S T S E A R C H

169

complement(int color)

{

if (color == WHITE) return(BLACK);

if (color == BLACK) return(WHITE);

return(UNCOLORED);

}

We can assign the first vertex in any connected component to be whatever

color/sex we wish. BFS can separate the men from the women, but we can’t tell

them apart just by using the graph structure.

Take-Home Lesson: Breadth-first and depth-first searches provide mechanisms

to visit each edge and vertex of the graph. They prove the basis of most simple,

efficient graph algorithms.