sequential_vertex_coloring

graph_tool.topology.sequential_vertex_coloring(g, order=None, color=None)

Returns a vertex coloring of the graph.

Parameters:

gGraph

Graph to be used.

orderVertexPropertyMap (optional, default: None)

Order with which the vertices will be colored.

colorVertexPropertyMap (optional, default: None)

Integer-valued vertex property map to store the colors.

Returns:

colorVertexPropertyMap

Integer-valued vertex property map with the vertex colors.

Notes

The time complexity is \(O(V(d+k))\), where \(V\) is the number of vertices, \(d\) is the maximum degree of the vertices in the graph, and \(k\) is the number of colors used.

References

[sgc-bgl]

http://www.boost.org/libs/graph/doc/sequential_vertex_coloring.html

[graph-coloring]

http://en.wikipedia.org/wiki/Graph_coloring

Examples

>>> g = gt.lattice([10, 10])
>>> colors = gt.sequential_vertex_coloring(g)
>>> print(colors.a)
[0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0
 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0]