 CoCalc Public Filestmp / 2018-05-01-092219.sagews
Author: William A. Stein
g = graphs.PetersenGraph()

g.chromatic_number?

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*.

module "sage.graphs.graph_coloring".

EXAMPLES:

sage: G = Graph({0: [1, 2, 3], 1: })
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(*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