CoCalc Public Filestmp / 2018-05-01-092219.sagewsOpen in with one click!
Author: William A. Stein
g = graphs.PetersenGraph()
File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/ 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