graph_tool.topology.sequential_vertex_coloring#

graph_tool.topology.sequential_vertex_coloring(g, order=None, color=None)[source]#

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

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]