Module Coloring.Mark
Provide a function for k
-coloring a graph with integer marks. The provided function is more efficient that the one provided by functor Make
above.
Parameters
Signature
val coloring : G.t -> int -> unit
coloring g k
colors the nodes of graphg
usingk
colors, assigning the marks integer values between 1 andk
.The graph marks may be partially set before starting; the meaning of initial values is as follows:
- 0: a node to be colored
- any value between 1 and
k
: a color already assigned - any value greater than
k
: a node to be ignored
- raises NoColoring
if
g
cannot bek
-colored.Worst-case time complexity is exponential. Space complexity is O(V).
val two_color : G.t -> unit
two_color g
attemps to colorg
with colors 1 and 2.- raises NoColoring
if this is not possible (i.e., if the graph is not bipartite). Runs in O(V+E).