Graph coloring

Vertex coloring assigns a color (integer label) to each vertex so that adjacent vertices have different colors. The smallest number of colors needed is the chromatic number χ(G). Exact minimum coloring is hard in general (NP-hard), so many practical systems use fast heuristics like greedy coloring.

1) Definitions

• Proper coloring: if edge (u,v) exists, then color[u] != color[v].
• Chromatic number: minimum number of colors among all proper colorings.
• Bipartite graph: exactly 2-colorable (if connected and has at least one edge).

2) Greedy coloring

Visit vertices in some order. For current vertex u, mark colors already used by colored neighbors, then assign the smallest available color. This is fast and always valid, but may use more colors than optimal depending on vertex order.

3) Example graph

Undirected edges: 0-1, 1-2, 2-0, 2-3, 3-4. The triangle 0-1-2 forces at least 3 colors.

   0
  / \
 1---2---3---4

One valid coloring:
0->C0, 1->C1, 2->C2, 3->C0, 4->C1

4) C — Greedy coloring (adjacency matrix)

#include <stdio.h>

#define V 5

static int g[V][V];
static int color[V];

static void add_edge(int u, int v) {
    g[u][v] = g[v][u] = 1;
}

int main(void) {
    add_edge(0, 1);
    add_edge(1, 2);
    add_edge(2, 0);
    add_edge(2, 3);
    add_edge(3, 4);

    for (int i = 0; i < V; i++) color[i] = -1;

    /* greedy order: 0,1,2,3,4 */
    for (int u = 0; u < V; u++) {
        int used[V] = {0};
        for (int v = 0; v < V; v++) {
            if (g[u][v] && color[v] != -1)
                used[color[v]] = 1;   /* neighbor color unavailable */
        }

        int c = 0;
        while (c < V && used[c]) c++;
        color[u] = c;   /* smallest feasible color */
    }

    int maxc = -1;
    for (int i = 0; i < V; i++) {
        printf("vertex %d -> color %d\n", i, color[i]);
        if (color[i] > maxc) maxc = color[i];
    }
    printf("colors used = %d\n", maxc + 1);
    return 0;
}

5) Complexity

• Greedy with matrix: O(V²) scanning neighbors and used colors.
• Greedy with adjacency list: roughly O(V + E) plus color-choice overhead.
• Exact chromatic number requires heavier search/optimization in general.

6) Trace — order 0,1,2,3,4