Graph Coloring¶

AUTHORS:

Tom Boothby (2008-02-21): Initial version
Carlo Hamalainen (2009-03-28): minor change: switch to C++ DLX solver
Nathann Cohen (2009-10-24): Coloring methods using linear programming

class sage.graphs.graph_coloring.Test¶

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)¶

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)

random_all_graph_colorings(tests=1000)¶

Verifies the results of all_graph_colorings() in three ways:

all colorings are unique
number of m-colorings 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.

TESTS:

sage: from sage.graphs.graph_coloring import Test
sage: Test().random_all_graph_colorings(1)

sage.graphs.graph_coloring.all_graph_colorings(G, n, count_only=False)¶

Computes all $n$ -colorings of the graph $G$ 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:

The first $|V|$ columns correspond to a vertex – a $1$ in this column indicates that that 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. Back-conversion to a coloring solution is a simple scan of the solutions, which will contain $|V| + (n-2)*|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://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.

sage.graphs.graph_coloring.chromatic_number(G)¶

Returns 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

sage.graphs.graph_coloring.edge_coloring(g, value_only=False, vizing=False, hex_colors=False, log=0)¶

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):
- When set to True, only the chromatic index is returned.
- When set to False, a partition of the edge set into matchings is returned if possible.
vizing – (default: False):
- When set to True, tries to find a $\Delta + 1$ -edge-coloring, where $\Delta$ is equal to the maximum degree in the graph.
- When set to False, tries to find a $\Delta$ -edge-coloring, where $\Delta$ is equal to the maximum degree in the graph. If impossible, tries to find and returns a $\Delta + 1$ -edge-coloring. This implies that value_only=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).
log – (default: 0) as edge-coloring is an $NP$ -complete problem, this function may take some time depending on the graph. Use log to define the level of verbosity you wantfrom the linear program solver. By default log=0, meaning that there will be no message printed by the solver.

OUTPUT:

In the following, $\Delta$ is equal to the maximum degree in the graph g.

If vizing=True and value_only=False, return a partition of the edge set into $\Delta + 1$ matchings.
If vizing=False and value_only=True, return the chromatic index.
If vizing=False and value_only=False, return a partition of the edge set into the minimum number of matchings.
If vizing=True and value_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$ .

EXAMPLE:

sage: from sage.graphs.graph_coloring import edge_coloring
sage: g = graphs.PetersenGraph()
sage: edge_coloring(g, value_only=True) # optional - requires GLPK or CBC
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

sage.graphs.graph_coloring.first_coloring(G, n=0, hex_colors=False)¶

Given a graph, and optionally a natural number $n$ , returns the first coloring we find with at least $n$ colors.

INPUT:

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).
n – The minimal number of colors to try.

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]]

sage.graphs.graph_coloring.number_of_n_colorings(G, n)¶

Given a graph $G$ and a natural number $n$ , returns the number of $n$ -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

sage.graphs.graph_coloring.numbers_of_colorings(G)¶

Returns the number of $n$ -colorings of the graph $G$ for $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, 72]

sage.graphs.graph_coloring.round_robin(n)¶

Computes a round-robin coloring of the complete graph on $n$ vertices.

A round-robin 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 round-robin coloring of the complete graph through the round-robin 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()
[(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

sage.graphs.graph_coloring.vertex_coloring(g, k=None, value_only=False, hex_colors=False, log=0)¶

Computes the chromatic number of the given graph or tests its $k$ -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 $k$ -colorable. The function returns a partition of the vertex set in $k$ independent sets if possible and False otherwise.
value_only – (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 – (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).
log – (default: 0) as vertex-coloring is an $NP$ -complete problem, this function may take some time depending on the graph. Use log to define the level of verbosity you want from the linear program solver. By default log=0, meaning that there will be no message printed by the solver.

OUTPUT:

If k=None and value_only=False, then return a partition of the vertex set into the minimum possible of independent sets.
If k=None and value_only=True, return the chromatic number.
If k is set and value_only=None, return False if the graph is not $k$ -colorable, and a partition of the vertex set into $k$ independent sets otherwise.
If k is set and value_only=True, test whether the graph is $k$ -colorable, and return True or False accordingly.

EXAMPLE:

sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.PetersenGraph()
sage: vertex_coloring(g, value_only=True) # optional - requires GLPK or CBC
3

Graph Coloring¶

Previous topic

Next topic

This Page

Navigation

Graph Coloring¶

Previous topic

Next topic

This Page

Quick search

Navigation