# igraph Reference Manual

For using the igraph C library

Search the manual:

# Chapter 17. Graph Coloring

## 1. `igraph_vertex_coloring_greedy` — Computes a vertex coloring using a greedy algorithm.

```int 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 non-negative 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 non-negative integers 0, 1, 2, ...

Arguments:

 `graph`: The input graph. `colors`: Pointer to an initialized integer vector. The vertex colors will be stored here. `heuristic`: The vertex ordering heuristic to use during greedy coloring. See `igraph_coloring_greedy_t`

Returns:

 Error code.

Example 17.1.  File `examples/simple/igraph_coloring.c`

```#include <igraph.h>
#include <assert.h>

int main() {
igraph_t graph;
igraph_vector_int_t colors;

igraph_rng_seed(igraph_rng_default(), 42);

igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 1000, 10000, /* directed = */ 0, /* loops = */ 0);

igraph_vector_int_init(&colors, 0);

igraph_vertex_coloring_greedy(&graph, &colors, IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS);

/* verify that the colouring is valid: */
{
long i;
long no_of_edges = igraph_ecount(&graph);
for (i = 0; i < no_of_edges; ++i) {
assert( VECTOR(colors)[ IGRAPH_FROM(&graph, i) ] != VECTOR(colors)[ IGRAPH_TO(&graph, i) ]  );
}
}

igraph_vector_int_destroy(&colors);
igraph_destroy(&graph);

return 0;
}
```

## 2. `igraph_coloring_greedy_t` — Ordering heuristics for greedy graph coloring.

```typedef enum {
IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS = 0
} igraph_coloring_greedy_t;
```

Ordering heuristics for `igraph_vertex_coloring_greedy()`.

Values:

 `IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS`: Choose vertex with largest number of already colored neighbors.