For using the igraph C library
igraph_error_t igraph_vertex_coloring_greedy(const igraph_t *graph, igraph_vector_int_t *colors, igraph_coloring_greedy_t heuristic);
This function assigns a "color"—represented as a nonnegative integer—to each vertex of the graph in such a way that neighboring vertices never have the same color. The obtained coloring is not necessarily minimal.
Vertices are colored one by one, choosing the smallest color index that differs from that of already colored neighbors. Colors are represented with nonnegative integers 0, 1, 2, ...
Arguments:

The input graph. 

Pointer to an initialized integer vector. The vertex colors will be stored here. 

The vertex ordering heuristic to use during greedy coloring. See 
Returns:
Error code. 
Example 18.1. File examples/simple/igraph_coloring.c
#include <igraph.h> int main() { igraph_t graph; igraph_vector_int_t colors; /* Setting a seed makes the result of erdos_renyi_game deterministic. */ igraph_rng_seed(igraph_rng_default(), 42); /* IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS are both equivalent to 0/FALSE, but communicate intent better in this context. */ igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 1000, 10000, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS); /* As with all igraph functions, the vector in which the result is returned must be initialized in advance. */ igraph_vector_int_init(&colors, 0); igraph_vertex_coloring_greedy(&graph, &colors, IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS); /* Verify that the colouring is valid, i.e. no two adjacent vertices have the same colour. */ { igraph_integer_t i; /* Store the edge count to avoid the overhead from igraph_ecount in the for loop. */ igraph_integer_t no_of_edges = igraph_ecount(&graph); for (i = 0; i < no_of_edges; ++i) { if ( VECTOR(colors)[ IGRAPH_FROM(&graph, i) ] == VECTOR(colors)[ IGRAPH_TO(&graph, i) ] ) { printf("Inconsistent coloring! Vertices %" IGRAPH_PRId " and %" IGRAPH_PRId " are adjacent but have the same color.\n", IGRAPH_FROM(&graph, i), IGRAPH_TO(&graph, i)); abort(); } } } /* Destroy data structure when we are done. */ igraph_vector_int_destroy(&colors); igraph_destroy(&graph); return 0; }
typedef enum { IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS = 0 } igraph_coloring_greedy_t;
Ordering heuristics for igraph_vertex_coloring_greedy()
.
Values:

Choose vertex with largest number of already colored neighbors. 
igraph_error_t igraph_is_perfect(const igraph_t *graph, igraph_bool_t *perfect);
A perfect graph is an undirected graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color.
Warning: This function may create the complement of the graph internally, which consumes a lot of memory. For moderately sized graphs, consider decomposing them into biconnected components and running the check separately on each component.
This implementation is based on the strong perfect graph theorem which was conjectured by Claude Berge and proved by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas.
Arguments:

The input graph. It is expected to be undirected and simple. 

Pointer to an integer, the result will be stored here. 
Returns:
Error code. 
Time complexity: worst case exponenital, often faster in practice.
← Chapter 17. Graph isomorphism  Chapter 19. Graph motifs, dyad census and triad census → 