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

module G : GM

Signature

val coloring : G.t -> int -> unit

coloring g k colors the nodes of graph g using k colors, assigning the marks integer values between 1 and k.

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 be k-colored.

    Worst-case time complexity is exponential. Space complexity is O(V).

val two_color : G.t -> unit

two_color g attemps to color g 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).