chromaticNumber -- computes the chromatic number of a hypergraph

Synopsis

Usage:

c = chromaticNumber H
Inputs:
- H, a hypergraph,
Outputs:
- c, an integer, the chromatic number of H

Description

Returns the chromatic number, the smallest number of colors needed to color the vertices of a graph. This method is based upon a result of Francisco-Ha-Van Tuyl that relates the chromatic number to an ideal membership problem.

i1 : S = QQ[a..f];

i2 : c4 = cycle(S,4) -- 4-cycle; chromatic number = 2

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, d}}}
           "ring" => S
           "vertices" => {a, b, c, d, e, f}

o2 : Graph

i3 : c5 = cycle(S,5) -- 5-cycle; chromatic number = 3

o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e, f}

o3 : Graph

i4 : k6 = completeGraph S  -- complete graph on 6 vertices; chromatic number = 6

o4 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {b, c}, {b, d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}, {d, e}, {d, f}, {e, f}}}
           "ring" => S
           "vertices" => {a, b, c, d, e, f}

o4 : Graph

i5 : chromaticNumber c4

o5 = 2

i6 : chromaticNumber c5

o6 = 3

i7 : chromaticNumber k6

o7 = 6

Caveat

This method should not be used with a hypergraph that has an edge of cardinality one since no coloring is possible.

Ways to use chromaticNumber:

chromaticNumber(HyperGraph)

For the programmer

The object chromaticNumber is a method function.