Graph coloring#
This module gathers all methods related to graph coloring. Here is what it can do :
Proper vertex coloring
Compute all \(n\)colorings a graph 

Return the first vertex coloring found 

Compute the number of \(n\)colorings of a graph 

Compute the number of colorings of a graph 

Return the chromatic number of the graph 

Compute vertex colorings and chromatic numbers 
Fractional relaxations
Return the fractional chromatic number of the graph 

Return the fractional chromatic index of the graph 
Other colorings
Compute Grundy numbers and Grundy colorings 

Compute bchromatic numbers and bcolorings 

Compute chromatic index and edge colorings 

Compute a roundrobin coloring of the complete graph on \(n\) vertices 

Compute the linear arboricity of the given graph 

Compute an acyclic edge coloring of the current graph 
AUTHORS:
Tom Boothby (20080221): Initial version
Carlo Hamalainen (20090328): minor change: switch to C++ DLX solver
Nathann Cohen (20091024): Coloring methods using linear programming
Methods#
 class sage.graphs.graph_coloring.Test[source]#
Bases:
object
This class performs randomized testing for
all_graph_colorings()
.Since everything else in this file is derived from
all_graph_colorings()
, this is a pretty good randomized tester for the entire file. Note that for a graph \(G\),G.chromatic_polynomial()
uses an entirely different algorithm, so we provide a good, independent test. random(tests=1000)[source]#
Call
self.random_all_graph_colorings()
.In the future, if other methods are added, it should call them, too.
 random_all_graph_colorings(tests=2)[source]#
Verify the results of
all_graph_colorings()
in three ways:all colorings are unique
number of mcolorings is \(P(m)\) (where \(P\) is the chromatic polynomial of the graph being tested)
colorings are valid – that is, that no two vertices of the same color share an edge.
 sage.graphs.graph_coloring.acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute an acyclic edge coloring of the current graph.
An edge coloring of a graph is a assignment of colors to the edges of a graph such that :
the coloring is proper (no adjacent edges share a color)
For any two colors \(i,j\), the union of the edges colored with \(i\) or \(j\) is a forest.
The least number of colors such that such a coloring exists for a graph \(G\) is written \(\chi'_a(G)\), also called the acyclic chromatic index of \(G\).
It is conjectured that this parameter cannot be too different from the obvious lower bound \(\Delta(G) \leq \chi'_a(G)\), \(\Delta(G)\) being the maximum degree of \(G\), which is given by the first of the two constraints. Indeed, it is conjectured that \(\Delta(G)\leq \chi'_a(G)\leq \Delta(G) + 2\).
INPUT:
hex_colors
– boolean (default:False
):If
hex_colors = True
, the function returns a dictionary associating to each color a list of edges (meant as an argument to theedge_colors
keyword of theplot
method).If
hex_colors = False
(default value), returns a list of graphs corresponding to each color class.
value_only
– boolean (default:False
):If
value_only = True
, only returns the acyclic chromatic index as an integer valueIf
value_only = False
, returns the color classes according to the value ofhex_colors
k
– integer; the number of colors to use.If
k > 0
, computes an acyclic edge coloring using \(k\) colors.If
k = 0
(default), computes a coloring of \(G\) into \(\Delta(G) + 2\) colors, which is the conjectured general bound.If
k = None
, computes a decomposition using the least possible number of colors.
solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
ALGORITHM:
Linear Programming
EXAMPLES:
The complete graph on 8 vertices cannot be acyclically edgecolored with less \(\Delta + 1\) colors, but it can be colored with \(\Delta + 2 = 9\):
sage: from sage.graphs.graph_coloring import acyclic_edge_coloring sage: g = graphs.CompleteGraph(8) sage: colors = acyclic_edge_coloring(g) # needs sage.numerical.mip
>>> from sage.all import * >>> from sage.graphs.graph_coloring import acyclic_edge_coloring >>> g = graphs.CompleteGraph(Integer(8)) >>> colors = acyclic_edge_coloring(g) # needs sage.numerical.mip
Each color class is of course a matching
sage: all(max(gg.degree()) <= 1 for gg in colors) # needs sage.numerical.mip True
>>> from sage.all import * >>> all(max(gg.degree()) <= Integer(1) for gg in colors) # needs sage.numerical.mip True
These matchings being a partition of the edge set:
sage: all(any(gg.has_edge(e) for gg in colors) # needs sage.numerical.mip ....: for e in g.edge_iterator(labels=False)) True
>>> from sage.all import * >>> all(any(gg.has_edge(e) for gg in colors) # needs sage.numerical.mip ... for e in g.edge_iterator(labels=False)) True
Besides, the union of any two of them is a forest
sage: all(g1.union(g2).is_forest() for g1 in colors for g2 in colors) # needs sage.numerical.mip True
>>> from sage.all import * >>> all(g1.union(g2).is_forest() for g1 in colors for g2 in colors) # needs sage.numerical.mip True
If one wants to acyclically color a cycle on \(4\) vertices, at least 3 colors will be necessary. The function raises an exception when asked to color it with only 2:
sage: g = graphs.CycleGraph(4) sage: acyclic_edge_coloring(g, k=2) # needs sage.numerical.mip Traceback (most recent call last): ... ValueError: this graph cannot be colored with the given number of colors
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(4)) >>> acyclic_edge_coloring(g, k=Integer(2)) # needs sage.numerical.mip Traceback (most recent call last): ... ValueError: this graph cannot be colored with the given number of colors
The optimal coloring give us \(3\) classes:
sage: colors = acyclic_edge_coloring(g, k=None) # needs sage.numerical.mip sage: len(colors) # needs sage.numerical.mip 3
>>> from sage.all import * >>> colors = acyclic_edge_coloring(g, k=None) # needs sage.numerical.mip >>> len(colors) # needs sage.numerical.mip 3
 sage.graphs.graph_coloring.all_graph_colorings(G, n, count_only=False, hex_colors=False, vertex_color_dict=False, color_classes=False)[source]#
Compute all \(n\)colorings of a graph.
This method casts the graph coloring problem into an exact cover problem, and passes this into an implementation of the Dancing Links algorithm described by Knuth (who attributes the idea to Hitotumatu and Noshita).
INPUT:
G
– a graphn
– a positive integer; the number of colorscount_only
– boolean (default:False
); when set toTrue
, it returns 1 for each coloring and ignores other parametershex_colors
– boolean (default:False
); when set toFalse
, colors are labeled [0, 1, …, \(n  1\)], otherwise the RGB Hex labeling is usedvertex_color_dict
– boolean (default:False
); when set toTrue
, it returns a dictionary{vertex: color}
, otherwise it returns a dictionary{color: [list of vertices]}
color_classes
– boolean (default:False
); when set toTrue
, the method returns only a list of the color classes and ignores parametershex_colors
andvertex_color_dict
Warning
This method considers only colorings using exactly \(n\) colors, even if a coloring using fewer colors can be found.
The construction works as follows. Columns:
The first \(V\) columns correspond to a vertex – a \(1\) in this column indicates that this vertex has a color.
After those \(V\) columns, we add \(n*E\) columns – a \(1\) in these columns indicate that a particular edge is incident to a vertex with a certain color.
Rows:
For each vertex, add \(n\) rows; one for each color \(c\). Place a \(1\) in the column corresponding to the vertex, and a \(1\) in the appropriate column for each edge incident to the vertex, indicating that that edge is incident to the color \(c\).
If \(n > 2\), the above construction cannot be exactly covered since each edge will be incident to only two vertices (and hence two colors)  so we add \(n*E\) rows, each one containing a \(1\) for each of the \(n*E\) columns. These get added to the cover solutions “for free” during the backtracking.
Note that this construction results in \(n*V + 2*n*E + n*E\) entries in the matrix. The Dancing Links algorithm uses a sparse representation, so if the graph is simple, \(E \leq V^2\) and \(n <= V\), this construction runs in \(O(V^3)\) time. Backconversion to a coloring solution is a simple scan of the solutions, which will contain \(V + (n2)*E\) entries, so runs in \(O(V^3)\) time also. For most graphs, the conversion will be much faster – for example, a planar graph will be transformed for \(4\)coloring in linear time since \(E = O(V)\).
REFERENCES:
http://wwwcsstaff.stanford.edu/~uno/papers/dancingcolor.ps.gz
EXAMPLES:
sage: from sage.graphs.graph_coloring import all_graph_colorings sage: G = Graph({0: [1, 2, 3], 1: [2]}) sage: n = 0 sage: for C in all_graph_colorings(G, 3, hex_colors=True): # needs sage.plot ....: parts = [C[k] for k in C] ....: for P in parts: ....: l = len(P) ....: for i in range(l): ....: for j in range(i + 1, l): ....: if G.has_edge(P[i], P[j]): ....: raise RuntimeError("Coloring Failed.") ....: n += 1 sage: print("G has %s 3colorings." % n) # needs sage.plot G has 12 3colorings.
>>> from sage.all import * >>> from sage.graphs.graph_coloring import all_graph_colorings >>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]}) >>> n = Integer(0) >>> for C in all_graph_colorings(G, Integer(3), hex_colors=True): # needs sage.plot ... parts = [C[k] for k in C] ... for P in parts: ... l = len(P) ... for i in range(l): ... for j in range(i + Integer(1), l): ... if G.has_edge(P[i], P[j]): ... raise RuntimeError("Coloring Failed.") ... n += Integer(1) >>> print("G has %s 3colorings." % n) # needs sage.plot G has 12 3colorings.
 sage.graphs.graph_coloring.b_coloring(g, k, value_only=True, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute bchromatic numbers and bcolorings.
This function computes a bcoloring with at most \(k\) colors that maximizes the number of colors, if such a coloring exists.
Definition :
Given a proper coloring of a graph \(G\) and a color class \(C\) such that none of its vertices have neighbors in all the other color classes, one can eliminate color class \(C\) assigning to each of its elements a missing color in its neighborhood.
Let a bvertex be a vertex with neighbors in all other colorings. Then, one can repeat the above procedure until a coloring is obtained where every color class contains a bvertex, in which case none of the color classes can be eliminated with the same idea. So, one can define a bcoloring as a proper coloring where each color class has a bvertex.
In the worst case, after successive applications of the above procedure, one get a proper coloring that uses a number of colors equal to the bchromatic number of \(G\) (denoted \(\chi_b(G)\)): the maximum \(k\) such that \(G\) admits a bcoloring with \(k\) colors.
A useful upper bound for calculating the bchromatic number is the following. If \(G\) admits a bcoloring with \(k\) colors, then there are \(k\) vertices of degree at least \(k  1\) (the bvertices of each color class). So, if we set \(m(G) = \max \{k  \text{there are } k \text{ vertices of degree at least } k  1 \}\), we have that \(\chi_b(G) \leq m(G)\).
Note
This method computes a bcoloring that uses at MOST \(k\) colors. If this method returns a value equal to \(k\), it cannot be assumed that \(k\) is equal to \(\chi_b(G)\). Meanwhile, if it returns any value \(k' < k\), this is a certificate that the Grundy number of the given graph is \(k'\).
As \(\chi_b(G)\leq m(G)\), it can be assumed that \(\chi_b(G) = k\) if
b_coloring(g, k)
returns \(k\) when \(k = m(G)\).INPUT:
k
– integer; maximum number of colorsvalue_only
– boolean (default:True
); when set toTrue
, only the number of colors is returned. Otherwise, the pair(nb_colors, coloring)
is returned, wherecoloring
is a dictionary associating its color (integer) to each vertex of the graph.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
ALGORITHM:
Integer Linear Program.
EXAMPLES:
The bchromatic number of a \(P_5\) is equal to 3:
sage: from sage.graphs.graph_coloring import b_coloring sage: g = graphs.PathGraph(5) sage: b_coloring(g, 5) # needs sage.numerical.mip 3
>>> from sage.all import * >>> from sage.graphs.graph_coloring import b_coloring >>> g = graphs.PathGraph(Integer(5)) >>> b_coloring(g, Integer(5)) # needs sage.numerical.mip 3
The bchromatic number of the Petersen Graph is equal to 3:
sage: g = graphs.PetersenGraph() sage: b_coloring(g, 5) # needs sage.numerical.mip 3
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> b_coloring(g, Integer(5)) # needs sage.numerical.mip 3
It would have been sufficient to set the value of
k
to 4 in this case, as \(4 = m(G)\).
 sage.graphs.graph_coloring.chromatic_number(G)[source]#
Return the chromatic number of the graph.
The chromatic number is the minimal number of colors needed to color the vertices of the graph \(G\).
EXAMPLES:
sage: from sage.graphs.graph_coloring import chromatic_number sage: G = Graph({0: [1, 2, 3], 1: [2]}) sage: chromatic_number(G) 3 sage: G = graphs.PetersenGraph() sage: G.chromatic_number() 3
>>> from sage.all import * >>> from sage.graphs.graph_coloring import chromatic_number >>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]}) >>> chromatic_number(G) 3 >>> G = graphs.PetersenGraph() >>> G.chromatic_number() 3
 sage.graphs.graph_coloring.edge_coloring(g, value_only=False, vizing=False, hex_colors=False, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute chromatic index and edge colorings.
INPUT:
g
– a graph.value_only
– boolean (default:False
):When set to
True
, only the chromatic index is returnedWhen set to
False
, a partition of the edge set into matchings is returned if possible
vizing
– boolean (default:False
):When set to
True
, finds an edge coloring using the algorithm described at [MG1992]. This always results in a coloring with \(\Delta + 1\) colors, where \(\Delta\) is equal to the maximum degree in the graph, even if one of the colors is empty, for the sake of consistency.When set to
False
, tries to find a \(\Delta\)edgecoloring using Mixed Integer Linear Programming (MILP). If impossible, returns a \((\Delta + 1)\)edgecoloring. Please note that determinating if the chromatic index of a graph equals \(\Delta\) is computationally difficult, and could take a long time.
hex_colors
– boolean (default:False
); when set toTrue
, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting)solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
OUTPUT:
In the following, \(\Delta\) is equal to the maximum degree in the graph
g
.If
vizing=True
andvalue_only=False
, return a partition of the edge set into \(\Delta + 1\) matchings.If
vizing=False
andvalue_only=True
, return the chromatic index.If
vizing=False
andvalue_only=False
, return a partition of the edge set into the minimum number of matchings.If
vizing=True
andvalue_only=True
, should return something, but mainly you are just trying to compute the maximum degree of the graph, and this is not the easiest way. By Vizing’s theorem, a graph has a chromatic index equal to \(\Delta\) or to \(\Delta + 1\).
Note
In a few cases, it is possible to find very quickly the chromatic index of a graph, while it remains a tedious job to compute a corresponding coloring. For this reason,
value_only = True
can sometimes be much faster, and it is a bad idea to compute the whole coloring if you do not need it !See also
Wikipedia article Edge_coloring for further details on edge coloring
EXAMPLES:
The Petersen graph has chromatic index 4:
sage: # needs sage.numerical.mip sage: from sage.graphs.graph_coloring import edge_coloring sage: g = graphs.PetersenGraph() sage: edge_coloring(g, value_only=True, solver='GLPK') 4 sage: color_classes = edge_coloring(g, value_only=False, solver='GLPK') sage: len(color_classes) 4 sage: len(set(frozenset(e) for C in color_classes for e in C)) == g.size() True sage: all(g.has_edge(e) for C in color_classes for e in C) True sage: all(len(Graph(C).matching()) == len(C) for C in color_classes) # needs networkx True sage: color_classes = edge_coloring(g, value_only=False, ....: hex_colors=True, solver='GLPK') sage: sorted(color_classes.keys()) ['#00ffff', '#7f00ff', '#7fff00', '#ff0000']
>>> from sage.all import * >>> # needs sage.numerical.mip >>> from sage.graphs.graph_coloring import edge_coloring >>> g = graphs.PetersenGraph() >>> edge_coloring(g, value_only=True, solver='GLPK') 4 >>> color_classes = edge_coloring(g, value_only=False, solver='GLPK') >>> len(color_classes) 4 >>> len(set(frozenset(e) for C in color_classes for e in C)) == g.size() True >>> all(g.has_edge(e) for C in color_classes for e in C) True >>> all(len(Graph(C).matching()) == len(C) for C in color_classes) # needs networkx True >>> color_classes = edge_coloring(g, value_only=False, ... hex_colors=True, solver='GLPK') >>> sorted(color_classes.keys()) ['#00ffff', '#7f00ff', '#7fff00', '#ff0000']
Complete graphs are colored using the lineartime roundrobin coloring:
sage: from sage.graphs.graph_coloring import edge_coloring sage: len(edge_coloring(graphs.CompleteGraph(20))) # needs sage.numerical.mip 19
>>> from sage.all import * >>> from sage.graphs.graph_coloring import edge_coloring >>> len(edge_coloring(graphs.CompleteGraph(Integer(20)))) # needs sage.numerical.mip 19
The chromatic index of a non connected graph is the maximum over its connected components:
sage: g = graphs.CompleteGraph(4) + graphs.CompleteGraph(10) sage: edge_coloring(g, value_only=True) # needs sage.numerical.mip 9
>>> from sage.all import * >>> g = graphs.CompleteGraph(Integer(4)) + graphs.CompleteGraph(Integer(10)) >>> edge_coloring(g, value_only=True) # needs sage.numerical.mip 9
 sage.graphs.graph_coloring.first_coloring(G, n=0, hex_colors=False)[source]#
Return the first vertex coloring found.
If a natural number \(n\) is provided, returns the first found coloring with at least \(n\) colors. That is, \(n\) is a lower bound on the number of colors to use.
INPUT:
n
– integer (default: 0); the minimal number of colors to tryhex_colors
– boolean (default:False
); when set toTrue
, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting)
EXAMPLES:
sage: from sage.graphs.graph_coloring import first_coloring sage: G = Graph({0: [1, 2, 3], 1: [2]}) sage: sorted(first_coloring(G, 3)) [[0], [1, 3], [2]]
>>> from sage.all import * >>> from sage.graphs.graph_coloring import first_coloring >>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]}) >>> sorted(first_coloring(G, Integer(3))) [[0], [1, 3], [2]]
 sage.graphs.graph_coloring.format_coloring(data, value_only=False, hex_colors=False, vertex_color_dict=False)[source]#
Helper method for vertex and edge coloring methods.
INPUT:
data
– either a number whenvalue_only
isTrue
or a list of color classesvalue_only
– boolean (default:False
); when set toTrue
, it simply returnsdata
hex_colors
– boolean (default:False
); when set toFalse
, colors are labeled [0, 1, …, \(n  1\)], otherwise the RGB Hex labeling is usedvertex_color_dict
– boolean (default:False
); when set toTrue
, it returns a dictionary{vertex: color}
, otherwise it returns a dictionary{color: [list of vertices]}
EXAMPLES:
sage: from sage.graphs.graph_coloring import format_coloring sage: color_classes = [['a', 'b'], ['c'], ['d']] sage: format_coloring(color_classes, value_only=True) [['a', 'b'], ['c'], ['d']] sage: format_coloring(len(color_classes), value_only=True) 3 sage: format_coloring(color_classes, value_only=False) {0: ['a', 'b'], 1: ['c'], 2: ['d']} sage: format_coloring(color_classes, value_only=False, hex_colors=True) # needs sage.plot {'#0000ff': ['d'], '#00ff00': ['c'], '#ff0000': ['a', 'b']} sage: format_coloring(color_classes, value_only=False, hex_colors=False, ....: vertex_color_dict=True) {'a': 0, 'b': 0, 'c': 1, 'd': 2} sage: format_coloring(color_classes, value_only=False, hex_colors=True, # needs sage.plot ....: vertex_color_dict=True) {'a': '#ff0000', 'b': '#ff0000', 'c': '#00ff00', 'd': '#0000ff'}
>>> from sage.all import * >>> from sage.graphs.graph_coloring import format_coloring >>> color_classes = [['a', 'b'], ['c'], ['d']] >>> format_coloring(color_classes, value_only=True) [['a', 'b'], ['c'], ['d']] >>> format_coloring(len(color_classes), value_only=True) 3 >>> format_coloring(color_classes, value_only=False) {0: ['a', 'b'], 1: ['c'], 2: ['d']} >>> format_coloring(color_classes, value_only=False, hex_colors=True) # needs sage.plot {'#0000ff': ['d'], '#00ff00': ['c'], '#ff0000': ['a', 'b']} >>> format_coloring(color_classes, value_only=False, hex_colors=False, ... vertex_color_dict=True) {'a': 0, 'b': 0, 'c': 1, 'd': 2} >>> format_coloring(color_classes, value_only=False, hex_colors=True, # needs sage.plot ... vertex_color_dict=True) {'a': '#ff0000', 'b': '#ff0000', 'c': '#00ff00', 'd': '#0000ff'}
 sage.graphs.graph_coloring.fractional_chromatic_index(G, solver='PPL', verbose_constraints=False, verbose=0)[source]#
Return the fractional chromatic index of the graph.
The fractional chromatic index is a relaxed version of edgecoloring. An edge coloring of a graph being actually a covering of its edges into the smallest possible number of matchings, the fractional chromatic index of a graph \(G\) is the smallest real value \(\chi_f(G)\) such that there exists a list of matchings \(M_1, \ldots, M_k\) of \(G\) and coefficients \(\alpha_1, \ldots, \alpha_k\) with the property that each edge is covered by the matchings in the following relaxed way
\[\forall e \in E(G), \sum_{e \in M_i} \alpha_i \geq 1.\]For more information, see the Wikipedia article Fractional_coloring.
ALGORITHM:
The fractional chromatic index is computed through Linear Programming through its dual. The LP solved by sage is actually:
\[\begin{split}\mbox{Maximize : }&\sum_{e\in E(G)} r_{e}\\ \mbox{Such that : }&\\ &\forall M\text{ matching }\subseteq G, \sum_{e\in M}r_{v}\leq 1\\\end{split}\]INPUT:
G
– a graphsolver
– (default:"PPL"
); specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.Note
The default solver used here is
"PPL"
which provides exact results, i.e. a rational number, although this may be slower that using other solvers. Be aware that this method may loop endlessly when using some non exact solvers as reported in Issue #23658 and Issue #23798.verbose_constraints
– boolean (default:False
); whether to display which constraints are being generatedverbose
– integer (default: \(0\)); sets the level of verbosity of the LP solver
EXAMPLES:
The fractional chromatic index of a \(C_5\) is \(5/2\):
sage: g = graphs.CycleGraph(5) sage: g.fractional_chromatic_index() # needs sage.numerical.mip 5/2
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(5)) >>> g.fractional_chromatic_index() # needs sage.numerical.mip 5/2
 sage.graphs.graph_coloring.fractional_chromatic_number(G, solver='PPL', verbose=0, check_components=True, check_bipartite=True)[source]#
Return the fractional chromatic number of the graph.
Fractional coloring is a relaxed version of vertex coloring with several equivalent definitions, such as the optimum value in a linear relaxation of the integer program that gives the usual chromatic number. It is also equal to the fractional clique number by LPduality.
ALGORITHM:
The fractional chromatic number is computed via the usual Linear Program. The LP solved by sage is essentially,
\[\begin{split}\mbox{Minimize : }&\sum_{I\in \mathcal{I}(G)} x_{I}\\ \mbox{Such that : }&\\ &\forall v\in V(G), \sum_{I\in \mathcal{I}(G),\, v\in I}x_{v}\geq 1\\ &\forall I\in \mathcal{I}(G), x_{I} \geq 0\end{split}\]where \(\mathcal{I}(G)\) is the set of maximal independent sets of \(G\) (see Section 2.1 of [CFKPR2010] to know why it is sufficient to consider maximal independent sets). As optional optimisations, we construct the LP on each biconnected component of \(G\) (and output the maximum value), and avoid using the LP if G is bipartite (as then the output must be 1 or 2).
Note
Computing the fractional chromatic number can be very slow. Since the variables of the LP are independent sets, in general the LP has size exponential in the order of the graph. In the current implementation a list of all maximal independent sets is created and stored, which can be both slow and memoryhungry.
INPUT:
G
– a graphsolver
– (default:"PPL"
); specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.Note
The default solver used here is
"PPL"
which provides exact results, i.e. a rational number, although this may be slower that using other solvers.verbose
– integer (default: \(0\)); sets the level of verbosity of the LP solvercheck_components
– boolean (default:True
); whether the method is called on each biconnected component of \(G\)check_bipartite
– boolean (default:True
); whether the graph is checked for bipartiteness. If the graph is bipartite then we can avoid creating and solving the LP.
EXAMPLES:
The fractional chromatic number of a \(C_5\) is \(5/2\):
sage: g = graphs.CycleGraph(5) sage: g.fractional_chromatic_number() # needs sage.numerical.mip 5/2
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(5)) >>> g.fractional_chromatic_number() # needs sage.numerical.mip 5/2
 sage.graphs.graph_coloring.grundy_coloring(g, k, value_only=True, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute Grundy numbers and Grundy colorings.
The method computes the worstcase of a firstfit coloring with less than \(k\) colors.
Definition:
A firstfit coloring is obtained by sequentially coloring the vertices of a graph, assigning them the smallest color not already assigned to one of its neighbors. The result is clearly a proper coloring, which usually requires much more colors than an optimal vertex coloring of the graph, and heavily depends on the ordering of the vertices.
The number of colors required by the worstcase application of this algorithm on a graph \(G\) is called the Grundy number, written \(\Gamma (G)\).
Equivalent formulation:
Equivalently, a Grundy coloring is a proper vertex coloring such that any vertex colored with \(i\) has, for every \(j < i\), a neighbor colored with \(j\). This can define a Linear Program, which is used here to compute the Grundy number of a graph.
Note
This method computes a grundy coloring using at MOST \(k\) colors. If this method returns a value equal to \(k\), it cannot be assumed that \(k\) is equal to \(\Gamma(G)\). Meanwhile, if it returns any value \(k' < k\), this is a certificate that the Grundy number of the given graph is \(k'\).
As \(\Gamma(G)\leq \Delta(G)+1\), it can also be assumed that \(\Gamma(G) = k\) if
grundy_coloring(g, k)
returns \(k\) when \(k = \Delta(G) +1\).INPUT:
k
– integer; maximum number of colorsvalue_only
– boolean (default:True
); when set toTrue
, only the number of colors is returned. Otherwise, the pair(nb_colors, coloring)
is returned, wherecoloring
is a dictionary associating its color (integer) to each vertex of the graph.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
ALGORITHM:
Integer Linear Program.
EXAMPLES:
The Grundy number of a \(P_4\) is equal to 3:
sage: from sage.graphs.graph_coloring import grundy_coloring sage: g = graphs.PathGraph(4) sage: grundy_coloring(g, 4) # needs sage.numerical.mip 3
>>> from sage.all import * >>> from sage.graphs.graph_coloring import grundy_coloring >>> g = graphs.PathGraph(Integer(4)) >>> grundy_coloring(g, Integer(4)) # needs sage.numerical.mip 3
The Grundy number of the PetersenGraph is equal to 4:
sage: g = graphs.PetersenGraph() sage: grundy_coloring(g, 5) # needs sage.numerical.mip 4
>>> from sage.all import * >>> g = graphs.PetersenGraph() >>> grundy_coloring(g, Integer(5)) # needs sage.numerical.mip 4
It would have been sufficient to set the value of
k
to 4 in this case, as \(4 = \Delta(G)+1\).
 sage.graphs.graph_coloring.linear_arboricity(g, plus_one=None, hex_colors=False, value_only=False, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute the linear arboricity of the given graph.
The linear arboricity of a graph \(G\) is the least number \(la(G)\) such that the edges of \(G\) can be partitioned into linear forests (i.e. into forests of paths).
Obviously, \(la(G)\geq \left\lceil \frac{\Delta(G)}{2} \right\rceil\).
It is conjectured in [Aki1980] that \(la(G)\leq \left\lceil \frac{\Delta(G)+1}{2} \right\rceil\).
INPUT:
plus_one
– integer (default:None
); whether to use \(\left\lceil \frac{\Delta(G)}{2} \right\rceil\) or \(\left\lceil \frac{\Delta(G)+1}{2} \right\rceil\) colors.If
0
, computes a decomposition of \(G\) into \(\left\lceil \frac{\Delta(G)}{2} \right\rceil\) forests of pathsIf
1
, computes a decomposition of \(G\) into \(\left\lceil \frac{\Delta(G)+1}{2} \right\rceil\) colors, which is the conjectured general bound.If
plus_one = None
(default), computes a decomposition using the least possible number of colors.
hex_colors
– boolean (default:False
):If
hex_colors = True
, the function returns a dictionary associating to each color a list of edges (meant as an argument to theedge_colors
keyword of theplot
method).If
hex_colors = False
(default value), returns a list of graphs corresponding to each color class.
value_only
– boolean (default:False
):If
value_only = True
, only returns the linear arboricity as an integer value.If
value_only = False
, returns the color classes according to the value ofhex_colors
solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
ALGORITHM:
Linear Programming
COMPLEXITY:
NPHard
EXAMPLES:
Obviously, a square grid has a linear arboricity of 2, as the set of horizontal lines and the set of vertical lines are an admissible partition:
sage: from sage.graphs.graph_coloring import linear_arboricity sage: g = graphs.Grid2dGraph(4, 4) # needs sage.numerical.mip sage: g1,g2 = linear_arboricity(g) # needs sage.numerical.mip
>>> from sage.all import * >>> from sage.graphs.graph_coloring import linear_arboricity >>> g = graphs.Grid2dGraph(Integer(4), Integer(4)) # needs sage.numerical.mip >>> g1,g2 = linear_arboricity(g) # needs sage.numerical.mip
Each graph is of course a forest:
sage: g1.is_forest() and g2.is_forest() # needs sage.numerical.mip True
>>> from sage.all import * >>> g1.is_forest() and g2.is_forest() # needs sage.numerical.mip True
Of maximum degree 2:
sage: max(g1.degree()) <= 2 and max(g2.degree()) <= 2 # needs sage.numerical.mip True
>>> from sage.all import * >>> max(g1.degree()) <= Integer(2) and max(g2.degree()) <= Integer(2) # needs sage.numerical.mip True
Which constitutes a partition of the whole edge set:
sage: all((g1.has_edge(e) or g2.has_edge(e)) # needs sage.numerical.mip ....: for e in g.edge_iterator(labels=None)) True
>>> from sage.all import * >>> all((g1.has_edge(e) or g2.has_edge(e)) # needs sage.numerical.mip ... for e in g.edge_iterator(labels=None)) True
 sage.graphs.graph_coloring.number_of_n_colorings(G, n)[source]#
Compute the number of \(n\)colorings of a graph
INPUT:
G
– a graphn
– a positive integer; the number of colors
EXAMPLES:
sage: from sage.graphs.graph_coloring import number_of_n_colorings sage: G = Graph({0: [1, 2, 3], 1: [2]}) sage: number_of_n_colorings(G, 3) 12
>>> from sage.all import * >>> from sage.graphs.graph_coloring import number_of_n_colorings >>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]}) >>> number_of_n_colorings(G, Integer(3)) 12
 sage.graphs.graph_coloring.numbers_of_colorings(G)[source]#
Compute the number of colorings of a graph.
Return the number of \(n\)colorings of the graph \(G\) for all \(n\) from \(0\) to \(V\).
EXAMPLES:
sage: from sage.graphs.graph_coloring import numbers_of_colorings sage: G = Graph({0: [1, 2, 3], 1: [2]}) sage: numbers_of_colorings(G) [0, 0, 0, 12, 24]
>>> from sage.all import * >>> from sage.graphs.graph_coloring import numbers_of_colorings >>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]}) >>> numbers_of_colorings(G) [0, 0, 0, 12, 24]
 sage.graphs.graph_coloring.round_robin(n)[source]#
Compute a roundrobin coloring of the complete graph on \(n\) vertices.
A roundrobin coloring of the complete graph \(G\) on \(2n\) vertices (\(V = [0, \dots, 2n  1]\)) is a proper coloring of its edges such that the edges with color \(i\) are all the \((i + j, i  j)\) plus the edge \((2n  1, i)\).
If \(n\) is odd, one obtain a roundrobin coloring of the complete graph through the roundrobin coloring of the graph with \(n + 1\) vertices.
INPUT:
n
– the number of vertices in the complete graph
OUTPUT:
A
CompleteGraph()
with labelled edges such that the label of each edge is its color.
EXAMPLES:
sage: from sage.graphs.graph_coloring import round_robin sage: round_robin(3).edges(sort=True) [(0, 1, 2), (0, 2, 1), (1, 2, 0)]
>>> from sage.all import * >>> from sage.graphs.graph_coloring import round_robin >>> round_robin(Integer(3)).edges(sort=True) [(0, 1, 2), (0, 2, 1), (1, 2, 0)]
sage: round_robin(4).edges(sort=True) [(0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 2, 0), (1, 3, 1), (2, 3, 2)]
>>> from sage.all import * >>> round_robin(Integer(4)).edges(sort=True) [(0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 2, 0), (1, 3, 1), (2, 3, 2)]
For higher orders, the coloring is still proper and uses the expected number of colors:
sage: g = round_robin(9) sage: sum(Set(e[2] for e in g.edges_incident(v)).cardinality() for v in g) == 2 * g.size() True sage: Set(e[2] for e in g.edge_iterator()).cardinality() 9
>>> from sage.all import * >>> g = round_robin(Integer(9)) >>> sum(Set(e[Integer(2)] for e in g.edges_incident(v)).cardinality() for v in g) == Integer(2) * g.size() True >>> Set(e[Integer(2)] for e in g.edge_iterator()).cardinality() 9
sage: g = round_robin(10) sage: sum(Set(e[2] for e in g.edges_incident(v)).cardinality() for v in g) == 2 * g.size() True sage: Set(e[2] for e in g.edge_iterator()).cardinality() 9
>>> from sage.all import * >>> g = round_robin(Integer(10)) >>> sum(Set(e[Integer(2)] for e in g.edges_incident(v)).cardinality() for v in g) == Integer(2) * g.size() True >>> Set(e[Integer(2)] for e in g.edge_iterator()).cardinality() 9
 sage.graphs.graph_coloring.vertex_coloring(g, k=None, value_only=False, hex_colors=False, solver=None, verbose=0, integrality_tolerance=0.001)[source]#
Compute Vertex colorings and chromatic numbers.
This function can compute the chromatic number of the given graph or test its \(k\)colorability.
See the Wikipedia article Graph_coloring for further details on graph coloring.
INPUT:
g
– a graph.k
– integer (default:None
); tests whether the graph is \(k\)colorable. The function returns a partition of the vertex set in \(k\) independent sets if possible andFalse
otherwise.value_only
– boolean (default:False
):When set to
True
, only the chromatic number is returned.When set to
False
(default), a partition of the vertex set into independent sets is returned if possible.
hex_colors
– boolean (default:False
); when set toTrue
, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting).solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
OUTPUT:
If
k=None
andvalue_only=False
, then return a partition of the vertex set into the minimum possible of independent sets.If
k=None
andvalue_only=True
, return the chromatic number.If
k
is set andvalue_only=None
, returnFalse
if the graph is not \(k\)colorable, and a partition of the vertex set into \(k\) independent sets otherwise.If
k
is set andvalue_only=True
, test whether the graph is \(k\)colorable, and returnTrue
orFalse
accordingly.
EXAMPLES:
sage: from sage.graphs.graph_coloring import vertex_coloring sage: g = graphs.PetersenGraph() sage: vertex_coloring(g, value_only=True) # needs sage.numerical.mip 3
>>> from sage.all import * >>> from sage.graphs.graph_coloring import vertex_coloring >>> g = graphs.PetersenGraph() >>> vertex_coloring(g, value_only=True) # needs sage.numerical.mip 3