AUTHORS:
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.chromatic_polynomial()
uses an entirely different algorithm, so we provide a good,
independent test.
Calls self.random_all_graph_colorings(). In the future, if other methods are added, it should call them, too.
TESTS:
sage: from sage.graphs.graph_coloring import Test
sage: Test().random(1)
Verifies the results of all_graph_colorings() in three ways:
TESTS:
sage: from sage.graphs.graph_coloring import Test
sage: Test().random_all_graph_colorings(1)
Computes 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 least number of colors such that such a coloring
exists for a graph is written
, also
called the acyclic chromatic index of
.
It is conjectured that this parameter can not be too different
from the obvious lower bound ,
being the maximum degree of
, which is given
by the first of the two constraints. Indeed, it is conjectured
that
.
INPUT:
hex_colors (boolean)
- If hex_colors = True, the function returns a dictionary associating to each color a list of edges (meant as an argument to the edge_colors keyword of the plot method).
- If hex_colors = False (default value), returns a list of graphs corresponding to each color class.
value_only (boolean)
- If value_only = True, only returns the acyclic chromatic index as an integer value
- If value_only = False, returns the color classes according to the value of hex_colors
k (integer) – the number of colors to use.
- If k>0, computes an acyclic edge coloring using
colors.
- If k=0 (default), computes a coloring of
into
colors, which is the conjectured general bound.
- If k=None, computes a decomposition using the least possible number of colors.
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbosity. Set to 0 by default, which means quiet.
ALGORITHM:
Linear Programming
EXAMPLE:
The complete graph on 8 vertices can not be acyclically
edge-colored with less colors, but it can be
colored with
:
sage: from sage.graphs.graph_coloring import acyclic_edge_coloring
sage: g = graphs.CompleteGraph(8)
sage: colors = acyclic_edge_coloring(g)
Each color class is of course a matching
sage: all([max(gg.degree())<=1 for gg in colors])
True
These matchings being a partition of the edge set:
sage: all([ any([gg.has_edge(e) for gg in colors]) for e in g.edges(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])
True
If one wants to acyclically color a cycle on 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)
Traceback (most recent call last):
...
ValueError: This graph can not be colored with the given number of colors.
The optimal coloring give us classes:
sage: colors = acyclic_edge_coloring(g, k=None)
sage: len(colors)
3
Computes all -colorings of the graph
by casting the graph
coloring problem into an exact cover problem, and passing this
into an implementation of the Dancing Links algorithm described
by Knuth (who attributes the idea to Hitotumatu and Noshita).
The construction works as follows. Columns:
Rows:
Note that this construction results in
entries in the matrix. The Dancing Links algorithm uses a
sparse representation, so if the graph is simple,
and
, this construction runs in
time.
Back-conversion to a coloring solution is a simple scan of the
solutions, which will contain
entries, so
runs in
time also. For most graphs, the conversion
will be much faster – for example, a planar graph will be
transformed for
-coloring in linear time since
.
REFERENCES:
http://www-cs-staff.stanford.edu/~uno/papers/dancing-color.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):
... 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 3-colorings."%n
G has 12 3-colorings.
TESTS:
sage: G = Graph({0:[1,2,3],1:[2]})
sage: for C in all_graph_colorings(G,0): print C
sage: for C in all_graph_colorings(G,-1): print C
Traceback (most recent call last):
...
ValueError: n must be non-negative.
Computes a b-coloring with at most k colors that maximizes the number of colors, if such a coloring exists
Definition :
Given a proper coloring of a graph and a color class
such
that none of its vertices have neighbors in all the other color
classes, one can eliminate color class
assigning to each of
its elements a missing color in its neighborhood.
Let a b-vertex 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 b-vertex, in which case none of the color classes can be eliminated with the same ideia. So, one can define a b-coloring as a proper coloring where each color class has a b-vertex.
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
the b-chromatic number of (denoted
):
the maximum
such that
admits a b-coloring with
colors.
An useful upper bound for calculating the b-chromatic number is
the following. If G admits a b-coloring with k colors, then there
are vertices of degree at least
(the b-vertices of
each color class). So, if we set
{
}, we have that
.
Note
This method computes a b-coloring that uses at MOST
colors. If this method returns a value equal to
, it can not
be assumed that
is equal to
. Meanwhile, if it
returns any value
, this is a certificate that the
Grundy number of the given graph is
.
As , it can be assumed that
if b_coloring(g, k) returns
when
.
INPUT:
ALGORITHM:
Integer Linear Program.
EXAMPLES:
The b-chromatic number of a is equal to 3:
sage: from sage.graphs.graph_coloring import b_coloring
sage: g = graphs.PathGraph(5)
sage: b_coloring(g, 5)
3
The b-chromatic number of the Petersen Graph is equal to 3:
sage: g = graphs.PetersenGraph()
sage: b_coloring(g, 5)
3
It would have been sufficient to set the value of k to 4 in
this case, as .
Returns the minimal number of colors needed to color the
vertices of the graph .
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
Properly colors the edges of a graph. See the URL http://en.wikipedia.org/wiki/Edge_coloring for further details on edge coloring.
INPUT:
g – a graph.
value_only – (default: False):
vizing – (default: False):
hex_colors – (default: False) when set to True, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting).
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbosity. Set to 0 by default, which means quiet.
OUTPUT:
In the following, is equal to the maximum degree in the graph
g.
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 !
EXAMPLE:
sage: from sage.graphs.graph_coloring import edge_coloring
sage: g = graphs.PetersenGraph()
sage: edge_coloring(g, value_only=True)
4
Complete graphs are colored using the linear-time round-robin coloring:
sage: from sage.graphs.graph_coloring import edge_coloring
sage: len(edge_coloring(graphs.CompleteGraph(20)))
19
Given a graph, and optionally a natural number , returns
the first coloring we find with at least
colors.
INPUT:
EXAMPLES:
sage: from sage.graphs.graph_coloring import first_coloring
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: first_coloring(G, 3)
[[1, 3], [0], [2]]
Computes the worst-case of a first-fit coloring with less than
colors.
Definition :
A first-fit 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 worst-case application of
this algorithm on a graph is called the Grundy number, written
.
Equivalent formulation :
Equivalently, a Grundy coloring is a proper vertex coloring such
that any vertex colored with has, for every
, a neighbor
colored with
. This can define a Linear Program, which is used
here to compute the Grundy number of a graph.
INPUT:
ALGORITHM:
Integer Linear Program.
EXAMPLES:
The Grundy number of a is equal to 3:
sage: from sage.graphs.graph_coloring import grundy_coloring
sage: g = graphs.PathGraph(4)
sage: grundy_coloring(g, 4)
3
The Grundy number of the PetersenGraph is equal to 4:
sage: g = graphs.PetersenGraph()
sage: grundy_coloring(g, 5)
4
It would have been sufficient to set the value of k to 4 in
this case, as .
Computes the linear arboricity of the given graph.
The linear arboricity of a graph is the least
number
such that the edges of
can be
partitioned into linear forests (i.e. into forests
of paths).
Obviously, .
It is conjectured in [Aki80] that
.
INPUT:
hex_colors (boolean)
- If hex_colors = True, the function returns a dictionary associating to each color a list of edges (meant as an argument to the edge_colors keyword of the plot method).
- If hex_colors = False (default value), returns a list of graphs corresponding to each color class.
value_only (boolean)
- 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 of hex_colors
k (integer) – the number of colors to use.
- If 0, computes a decomposition of
into
forests of paths
- If 1 (default), computes a decomposition of
into
colors, which is the conjectured general bound.
- If k=None, computes a decomposition using the least possible number of colors.
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbosity. Set to 0 by default, which means quiet.
ALGORITHM:
Linear Programming
COMPLEXITY:
NP-Hard
EXAMPLE:
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.GridGraph([4,4])
sage: g1,g2 = linear_arboricity(g, k=0)
Each graph is of course a forest:
sage: g1.is_forest() and g2.is_forest()
True
Of maximum degree 2:
sage: max(g1.degree()) <= 2 and max(g2.degree()) <= 2
True
Which constitutes a partition of the whole edge set:
sage: all([g1.has_edge(e) or g2.has_edge(e) for e in g.edges(labels = None)])
True
REFERENCES:
[Aki80] | Akiyama, J. and Exoo, G. and Harary, F. Covering and packing in graphs. III: Cyclic and acyclic invariants Mathematical Institute of the Slovak Academy of Sciences Mathematica Slovaca vol30, n4, pages 405–417, 1980 |
Given a graph and a natural number
, returns the number of
-colorings of the graph.
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
Returns the number of -colorings of the graph
for
from
to
.
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, 72]
Computes a round-robin coloring of the complete graph on vertices.
A round-robin coloring of the complete graph on
vertices
(
) is a proper coloring of its edges such that
the edges with color
are all the
plus the
edge
.
If is odd, one obtain a round-robin coloring of the complete graph
through the round-robin coloring of the graph with
vertices.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.graphs.graph_coloring import round_robin
sage: round_robin(3).edges()
[(0, 1, 2), (0, 2, 1), (1, 2, 0)]
sage: round_robin(4).edges()
[(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
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
Computes the chromatic number of the given graph or tests its
-colorability. See http://en.wikipedia.org/wiki/Graph_coloring for
further details on graph coloring.
INPUT:
g – a graph.
k – (default: None) tests whether the graph is -colorable.
The function returns a partition of the vertex set in
independent
sets if possible and False otherwise.
value_only – (default: False):
hex_colors – (default: False) when set to True, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting).
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbosity. Set to 0 by default, which means quiet.
OUTPUT:
EXAMPLE:
sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.PetersenGraph()
sage: vertex_coloring(g, value_only=True)
3