Graph Coloring

Assign labels (colors) to vertices or edges so that no two adjacent elements share the same color. The minimum number of colors needed is the chromatic number (vertices) or chromatic index (edges).

Algorithm What it does

Algorithm	What it does
Sequential Vertex Coloring	Greedy vertex coloring in O(V(d+k)) where d is max degree and k the number of colors used. The color count depends on the vertex ordering; combine with `smallest_last_vertex_ordering` for better results.
Edge Coloring	Colors edges so no two edges sharing a vertex have the same color. Runs in _O(
E
V	)_ using the Misra-Gries variant of Vizing’s theorem; uses at most `max_degree(g) + 1` colors.
Is Bipartite	Tests if a graph can be 2-colored (vertices split into two independent sets).
Find Odd Cycle	If the graph is not bipartite, returns an odd-length cycle as proof.

Sequential Vertex Coloring

Greedy vertex coloring in O(V(d+k)) where d is max degree and k the number of colors used. The color count depends on the vertex ordering; combine with smallest_last_vertex_ordering for better results.

Edge Coloring

Colors edges so no two edges sharing a vertex have the same color. Runs in _O(

)_ using the Misra-Gries variant of Vizing’s theorem; uses at most max_degree(g) + 1 colors.

Is Bipartite

Tests if a graph can be 2-colored (vertices split into two independent sets).

Find Odd Cycle

If the graph is not bipartite, returns an odd-length cycle as proof.

Vertex coloring is NP-hard in general [25]. sequential_vertex_coloring is a fast heuristic that does not guarantee the minimum number of colors. For exact 2-colorability, use is_bipartite.

Edit this Page