File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py
Signature : g.chromatic_number(self, algorithm='DLX', verbose=0)
Docstring :
Returns the minimal number of colors needed to color the vertices
of the graph G.
INPUT:
* "algorithm" -- Select an algorithm from the following supported
algorithms:
* If "algorithm="DLX"" (default), the chromatic number is
computed using the dancing link algorithm. It is inefficient
speedwise to compute the chromatic number through the dancing
link algorithm because this algorithm computes *all* the
possible colorings to check that one exists.
* If "algorithm="CP"", the chromatic number is computed using
the coefficients of the chromatic polynomial. Again, this
method is inefficient in terms of speed and it only useful for
small graphs.
* If "algorithm="MILP"", the chromatic number is computed using
a mixed integer linear program. The performance of this
implementation is affected by whether optional MILP solvers
have been installed (see the "MILP module", or Sage's tutorial
on Linear Programming).
* "verbose" -- integer (default: "0"). Sets the level of
verbosity for the MILP algorithm. Its default value is 0, which
means *quiet*.
See also: For more functions related to graph coloring, see the
module "sage.graphs.graph_coloring".
EXAMPLES:
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: G.chromatic_number(algorithm="DLX")
3
sage: G.chromatic_number(algorithm="MILP")
3
sage: G.chromatic_number(algorithm="CP")
3
A bipartite graph has (by definition) chromatic number 2:
sage: graphs.RandomBipartite(50,50,0.7).chromatic_number()
2
A complete multipartite graph with k parts has chromatic number k:
sage: all(graphs.CompleteMultipartiteGraph([5]*i).chromatic_number() == i for i in range(2,5))
True
The complete graph has the largest chromatic number from all the
graphs of order n. Namely its chromatic number is n:
sage: all(graphs.CompleteGraph(i).chromatic_number() == i for i in range(10))
True
The Kneser graph with parameters (n,2) for n > 3 has chromatic
number n-2:
sage: all(graphs.KneserGraph(i,2).chromatic_number() == i-2 for i in range(4,6))
True
A snark has chromatic index 4 hence its line graph has chromatic
number 4:
sage: graphs.FlowerSnark().line_graph().chromatic_number()
4