color_graph_greedy {gor}

Greedy coloring of a graph

Description

Greedy algorithm for coloring the vertices of a graph

Usage

color_graph_greedy(g, ord = NULL, ran = FALSE)

Arguments

g

Graph to be colored

ord

Specified vertex ordering or NULL if natural vertex ordering is preferred

ran

Choose random vertex ordering; it defaults to FALSE. It is ignored if ord is non-NULL

Details

"Colors" are integers from 1 to the order of the graph to be colored. The greedy strategy assigns to each vertex v the least color not assigned to the neighbors of v.

Value

Vertex colors in a vector, with component i being the (integer) color of vertex i.

Author(s)

Cesar Asensio

Examples

library(igraph)
g <- make_graph("Petersen")
cg <- color_graph_greedy(g)
plot(g, vertex.color = rainbow(6)[cg])
max(cg)         # = 3: Number of colors used by the algorithm
sum(g[cg == 1, cg == 1])  # = 0: Color classes are stable sets

g <- make_graph("Dodecahedron")
cg <- color_graph_greedy(g)
plot(g, vertex.color = rainbow(6)[cg])
max(cg)   # = 4: Number of colors used by the algorithm
sum(g[cg == 1, cg == 1])  # = 0: Color classes are stable sets

## However, the dodecahedron has a 3-coloring:
cdod <- rep(1, 20)
cdod[c(1,3,7,12,13,20)] <- 2
cdod[c(5,8,9,11,17,19)] <- 3
plot(g, vertex.color = rainbow(6)[cdod])
sum(g[cdod == 1, cdod == 1]) # = 0
sum(g[cdod == 2, cdod == 2]) # = 0
sum(g[cdod == 3, cdod == 3]) # = 0

## Some vertex orderings can use less colors:
cg <- color_graph_greedy(g, ord = 20:1)
plot(g, vertex.color = rainbow(6)[cg])
max(cg)         # = 3: Number of colors used by the algorithm