Module coloring 

Graph coloring algorithms.

ALGO-CL-001: vertex_coloring_greedy — heuristic greedy vertex coloring with two ordering strategies (DSATUR and Colored-Neighbors).

Also provides three coloring validators:

• is_vertex_coloring — check proper vertex coloring
• is_bipartite_coloring — check bipartite (2-color) vertex coloring
• is_edge_coloring — check proper edge coloring

Reference: references/igraph/src/misc/coloring.c (519 lines).

Structs

BipartiteColoringResult

Result of is_bipartite_coloring.

Enums

BipartiteEdgeDirection

Edge direction pattern in a directed bipartite graph.

GreedyColoringHeuristic

Heuristic ordering strategy for vertex_coloring_greedy.

Functions

chromatic_number_upper_bound

Compute an upper bound on the vertex chromatic number using greedy DSatur coloring.

edge_chromatic_number

Return the number of distinct colors used by an edge coloring.

edge_coloring_greedy

Compute a greedy edge coloring.

is_bipartite_coloring

Checks whether the given boolean type assignment is a valid bipartite coloring, i.e. no two adjacent vertices have the same type. Self-loops are ignored.

is_edge_coloring

Checks whether the given edge color assignment is a valid edge coloring, i.e. no two edges sharing a vertex have the same color. Self-loops are not considered adjacent to themselves.

is_vertex_coloring

Checks whether the given color assignment is a valid vertex coloring, i.e. no two adjacent vertices share the same color. Self-loops are ignored.

vertex_chromatic_number

Return the number of distinct colors used in a vertex coloring.

vertex_coloring_greedy

Computes a vertex coloring using a greedy algorithm.