The Vertex Coloring AlgorithmAshay DharwadkerMathematics & Natural Sciences H-501 Palam Vihar District Gurgaon Haryana 122017 India |
 |
|
We present a new polynomial-time
algorithm for finding proper m-colorings of the vertices of a graph.
We prove that every graph with
n vertices and maximum vertex degree
Δ
must have chromatic number χ(G) less
than or equal to Δ+1 and that the algorithm
will always find a proper m-coloring of the vertices of G
with m less than or equal to Δ+1. Furthermore,
we prove that this condition is the best possible in terms of n
and Δ by explicitly constructing graphs for
which the chromatic number is exactly
Δ+1. In
the special case when G is a connected simple graph and is neither
an odd cycle nor a complete graph, we show that the algorithm will always
find a proper m-coloring of the vertices of G with m
less than or equal to Δ. In the process, we
obtain a new constructive proof of Brooks' famous theorem of 1941. For
all known examples of graphs, the algorithm finds a proper m-coloring
of the vertices of the graph G for m equal to the chromatic
number χ(G). In view of the importance
of the P versus
NP question, we ask: does there exist
a graph G for which this algorithm cannot find a proper m-coloring of the
vertices of G with m equal to the chromatic number χ(G)?
The algorithm is demonstrated with several examples of famous graphs, including
a proper four-coloring of the map of India and two large Mycielski benchmark
graphs with hidden minimum vertex colorings. We implement the algorithm
in C++ and provide a demonstration program for Microsoft Windows [download]. Google Scholar Citations © 2006
|
 |
|
Thanks to Klaus D. Witzel
for suggesting the Mycielski graphs of Examples 7.19 and 7.20 that serve
as the main benchmarks for testing whether this algorithm actually finds
a minimum vertex coloring in the hardest known cases. This algorithm has also been cited in
Applications of Graph Theory published by the
Korean Society for Industrial and Applied Mathematics. We are pleased to announce that
The Vertex Coloring Algorithm has been published by
Amazon in 2011. The Endowed Chair of the Institute of Mathematics was bestowed upon
Distinguished Professor Ashay Dharwadker in 2012 to honour his fundamental contributions to Mathematics and Natural Sciences.
|
 |
|
In 1972, Karp [1]
introduced a list of twenty-one
NP-complete problems, one of which
was the problem of trying to find a proper m-coloring of the vertices
of a graph, where m is a fixed integer greater than 2. Given a graph
and a set of m colors, one must find out if it is possible to assign
a color to each vertex such that no two adjacent vertices are assigned
the same color. Such an assignment is called a proper
m-coloring
of the vertices of a graph. Even if such a coloring exists, it can be very
difficult to find in general. For example, try to find a proper 3-coloring
of the vertices of the Frucht graph
[2] shown below
in Figure 1.1.
We present a new polynomial-time VERTEX COLORING ALGORITHM for finding proper m-colorings of the vertices of a graph. In Section 2, we provide precise DEFINITIONS of all the terminology used. In Section 3, we present a formal description of the ALGORITHM followed by a small example to show how the algorithm works step-by-step. In Section 4, we show that the algorithm has polynomial-time COMPLEXITY. In Section 5, we establish conditions of SUFFICIENCY for a graph to have a proper m-coloring. We prove that every graph with n vertices and maximum vertex degree Δ must have chromatic number χ(G) less than or equal to Δ+1 and that the algorithm will always find a proper m-coloring of the vertices of G with m less than or equal to Δ+1. Furthermore, we prove that this condition is the best possible in terms of n and Δ by explicitly constructing graphs for which the chromatic number is exactly Δ+1. In the special case when G is a connected simple graph and is neither an odd cycle nor a complete graph, we show that the algorithm will always find a proper m-coloring of the vertices of G with m less than or equal to Δ. In the process, we obtain a new constructive proof of Brooks' famous theorem of 1941. For all known examples of graphs, the algorithm finds a proper m-coloring of the vertices of the graph G for m equal to the chromatic number χ(G). In view of the importance of the P versus NP question [3], we ask: does there exist a graph G for which this algorithm cannot find a proper m-coloring of the vertices of G with m equal to the chromatic number χ(G)? In Section 6, we provide an IMPLEMENTATION of the algorithm as a C++ program, together with demonstration software for Microsoft Windows. In Section 7, we demonstrate the algorithm with several EXAMPLES of famous graphs, including a proper four-coloring of the map of India and two large Mycielski benchmark graphs with hidden minimum vertex colorings. In Section 8, we list the REFERENCES. |
|
We begin with precise definitions of all
the terminology and notation used in this presentation, following [4].
We use the usual notation
⌊x⌋
to denote the floor function i.e. the greatest integer not greater
than x and ⌈x⌉
to denote the ceiling function i.e. the least integer not less than
x.
A simple graph G with n vertices consists of a set of vertices V, with |V| = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. Note that the definition of G explicitly forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite. We may label the vertices of G with the integers 1, 2, ..., n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is a neighbor of v (or u is adjacent to v) and write uv∈E. Neighborhood is clearly a symmetric relationship: uv∈E if and only if vu∈E. The degree of a vertex v, denoted by d(v), is the number of neighbors of v. The maximum degree over all vertices of G is denoted by Δ. The adjacency matrix of G is an n×n matrix with the entry in row u and column v equal to 1 if uv∈E and equal to 0 otherwise. Given graphs G and H, the Cartesian product G×H is defined as the graph whose set of vertices is V(G)×V(H) with an edge connecting vertex (u1,v1) with vertex (u2,v2) if and only if either u1 = u2 and {v1, v2} is an edge in H or v1 = v2 and {u1, u2} is an edge in G. A clique Q of a graph G is a subset of vertices such that every unordered pair of vertices in Q is an edge. If all the vertices of a graph form a clique then the graph is said to be complete. A complete graph with m vertices is denoted by Km. An independent set S of a graph G is a set of vertices such that no unordered pair of vertices in S is an edge. Given an independent set S of G and a vertex v outside S, we say that v is adjoinable if the set S∪{v} is still an independent set of G. Denote by ρ(S) the number of adjoinable vertices of an independent set S of G. A maximal independent set has no adjoinable vertices. A maximum independent set is an independent set with the largest number of vertices. Note that a maximum independent set is always maximal but not necessarily vice versa. Given a set of m colors {1, 2, ..., m}, a proper m-coloring of the vertices of a graph G is an assignment of a unique color to each vertex of G such that no two adjacent vertices are assigned the same color. The chromatic number χ(G) of a graph G is the minimum value of m for which there exists a a proper m-coloring of the vertices of G. An algorithm is a problem-solving method suitable for implementation as a computer program. While designing algorithms we are typically faced with a number of different approaches. For small problems, it hardly matters which approach we use, as long as it is one that solves the problem correctly. However, there are many problems for which the only known algorithms take so long to compute the solution that they are practically useless. A polynomial-time algorithm is one whose number of computational steps is always bounded by a polynomial function of the size of the input. Thus, a polynomial-time algorithm is one that is actually useful in practice. The class of all such problems that have polynomial-time algorithms is denoted by P. For some problems, there are no known polynomial-time algorithms but these problems do have nondeterministic polynomial-time algorithms: try all candidates for solutions simultaneously and for each given candidate, verify whether it is a correct solution in polynomial-time. The class of all such problems is denoted by NP. Clearly P ⊆ NP. On the other hand, there are problems that are known to be in NP and are such that any polynomial-time algorithm for them can be transformed (in polynomial-time) into a polynomial-time algorithm for every problem in NP. Such problems are called NP-complete. The problem of trying to find a proper m-coloring of the vertices of a graph, for any fixed integer m greater than 2, is known to be NP-complete [1]. Thus, if we are able to show the existence of a polynomial-time algorithm that finds a proper m-coloring of the vertices of a graph (whenever such a coloring exists, for a fixed integer m greater than 2), we could prove that P = NP. The present algorithm is, so far as we know, a promising candidate for the task. One of the greatest unresolved problems in mathematics and computer science today is whether P = NP or P ≠ NP [3]. |
|
We now present a formal description of
the algorithm. This is followed by a small example illustrating the steps
of the algorithm. We start with the Cartesian Lemma [15]
that allows us to convert the problem of finding a proper m-coloring
of the n vertices of a graph to the logically equivalent problem
of finding an independent set of size n in the Cartesian product
G×Km.
The Cartesian Lemma. A simple graph G with n vertices is m-colorable if and only if the Cartesian product G×Km has an independent set of size n. Proof. Suppose there is a proper m-coloring of the vertices of G. Define a subset S of vertices of the Cartesian product G×Km as follows. A vertex (u, v) of G×Km belongs to S if and only if the vertex u of G is assigned the color v with respect to the proper m-coloring. Since each vertex of G is assigned a unique color, |S| = n. We shall now show that S is an independent set. Given (u1, v1) and (u2, v2) in S, suppose there is an edge {(u1, v1), (u2, v2)} in G×Km. Then, by definition of the Cartesian product, there are two possibilities:
Conversely, suppose there is an independent set S of size n in the Cartesian product G×Km. We shall show that G has a proper m-coloring. If m is greater than or equal to n then G can be trivially m-colored, so assume that m is less than n. Partition the vertices of S into at most m equivalence classes C1, C2, ..., Cm where a vertex (u, v) in S belongs to the equivalence class Ci if and only if v = vi. Clearly, this gives a well-defined partition of the vertices of S. Now partition the vertices of G into at most m equivalence classes C'1, C'2, ..., C'm where a vertex u of G belongs to the equivalence class C'i if and only if (u, vi) belongs to the equivalence class Ci. To show that this gives a well-defined partition of the vertices of G observe that:
We now define two procedures for working with independent sets in the Cartesian product G×Km. 3.1. Procedure. Given an independent set S of the Cartesian product G×Km, if S has no adjoinable vertices, output S. Else, for each adjoinable vertex (u, v) of S, find the number ρ(S∪{(u, v)}) of adjoinable vertices of the independent set S∪{(u, v)}. Let (u, v)max denote an adjoinable vertex such that ρ(S∪{(u, v)max}) is a maximum and obtain the independent set S∪{(u, v)max}. Repeat until the independent set has no adjoinable vertices. 3.2. Procedure. Given a maximal independent set S of the Cartesian product G×Km, if there is no vertex (u1, v1) outside S such that (u1, v1) has exactly one neighbor (u2,v2) inside S, output S. Else, find a vertex (u1, v1) outside S such that (u1, v1) has exactly one neighbor (u2, v2) inside S. Define S(u1, v1), (u2, v2) by adjoining (u1, v1) to S and removing (u2, v2) from S. Perform procedure 3.1 on S(u1, v1), (u2, v2) and output the resulting independent set. 3.3. Algorithm. Given as input a simple graph G with n vertices, search for a proper m-coloring of the vertices of G. Let {u1, u2, ..., un} denote the vertices of G and let {v1, v2, ..., vm} denote the vertices of Km. We generate maximal independent sets in the Cartesian product G×Km. At each stage, if the independent set obtained has size at least n, then go to part III.
The algorithm first constructs the Cartesian product G×K3
shown below in figure 3.2 with 12 vertices {(1,1), (1,2), (1,3), (2,1),
(2,2), (2,3), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)}. We construe the
vertices {1, 2, 3} of the second component K3 as the
colors green, red and blue respectively.
The algorithm now searches for an independent set of size 4 in the Cartesian product G×K3. Part I for i = 1 and j = 1 initializes the independent set as S1,1 = {(1, 1)}. We now perform procedure 3.1. Here are the results in tabular form:
We obtain a maximal independent set S1,1 = {(1, 1), (2, 2), (3, 3), (4, 2)} of the required size n = 4. Now part III outputs S1,1 as the requested proper 3-coloring of the input graph G and the algorithm terminates. Note that we interpret the result as follows: vertex 1 is colored with color 1 (green), vertex 2 is colored with color 2 (red), vertex 3 is colored with color 3 (blue) and vertex 4 is colored with color 2 (red). |
|
We shall now show that the algorithm terminates
in polynomial-time while searching for a proper m-coloring for a
graph with n vertices, by specifying a polynomial of N =
nm
that is an upper bound on the total number of computational steps performed
by the algorithm. Note that we consider
4.1. Proposition. Given a simple graph G with n vertices and an independent set S of G×Km, procedure 3.1 takes at most (nm)5 steps. Proof. Checking whether a particular vertex is adjoinable takes at most (nm)2 steps, since the vertex has less than nm neighbors and for each neighbor it takes less than nm steps to check whether it is outside the independent set. For a particular independent set, finding the number ρ of adjoinable vertices takes at most (nm)3 = (nm)(nm)2 steps, since for each of the at most nm vertices outside the independent set we must check whether it is adjoinable or not. For a particular independent set, finding a vertex for which ρ is maximum then takes at most (nm)4 = (nm)(nm)3 steps, since there are at most nm vertices outside. Procedure 3.1 terminates when at most nm vertices are adjoined, so it takes a total of at most (nm)5 = (nm)(nm)4 steps. ☐ 4.2. Proposition. Given a simple graph G with n vertices and a maximal independent set S of G×Km, procedure 3.2 takes at most (nm)5+(nm)2+1 steps. Proof. To find a vertex (u1, v1) outside S that has exactly one neighbor (u2, v2) inside S takes at most (nm)2 steps, since there are less than nm vertices outside S and we must find out if at least one of the less than nm neighbors of any such vertex are inside S. If such a vertex (u1, v1) has been found, it takes one step to exchange (u1, v1) and (u2, v2). Thereafter, by proposition 4.1, it takes at most (nm)5 steps to perform procedure 3.1 on the resulting independent set. Thus, procedure 3.2 takes at most (nm)2+1+(nm)5 steps. ☐ 4.3. Proposition. Given a simple graph G with n vertices and m colors, part I of the algorithm takes at most (nm)7+(nm)6+(nm)4+(nm)2 steps. Proof. At each turn, procedure 3.1 takes at most (nm)5 steps by proposition 4.1. Then procedure 3.2 is performed at most nm times which, by proposition 4.2, takes at most nm((nm)5+(nm)2+1) = (nm)6+(nm)3+nm steps. So, at each turn, at most (nm)5+(nm)6+(nm)3+nm steps are executed. There are nm turns for i = 1, 2, ..., n, and j = 1, 2, ..., m, so part I performs a total of at most nm((nm)5+(nm)6+(nm)3+nm) = (nm)6+(nm)7+(nm)4+(nm)2 steps. ☐ 4.4. Proposition. Given a simple graph G with n vertices and m colors, the algorithm takes less than (nm)8+2(nm)7+(nm)6+(nm)5+(nm)4+(nm)3+(nm)2 steps to terminate. Proof. There are less than (nm)2 distinct pairs of maximal independent sets found by part I, that are treated in turn. Similar to the proof of proposition 4.3, part II takes less than (nm)2((nm)5+(nm)6+(nm)3+nm) = (nm)7+(nm)8+(nm)5+(nm)3. Hence, part I and part II together take less than a grand total of ((nm)7+(nm)6+(nm)4+(nm)2)+((nm)8+(nm)7+(nm)5+(nm)3) = (nm)8+2(nm)7+(nm)6+(nm)5+(nm)4+(nm)3+(nm)2 steps to terminate. ☐ 4.5. Remark. These are pessimistic upper bounds for the worst possible cases. The actual number of steps taken by the algorithm will depend on both n and m and, for all the known cases when a proper m-coloring of the vertices exists, the algorithm terminates much faster. In all of the examples in section 7, one or two steps of part I already find a proper m-coloring of the vertices of the graph. |
|
Given m colors, the algorithm may
be applied to any simple graph G with n vertices. The algorithm
will always terminate in polynomial-time, finding many maximal independent
sets in the Cartesian product G×Km.
The propositions below establish sufficient conditions on the number of
colors m and the input graph G, which guarantee that the
algorithm will find maximal independent sets of size at least n
in the Cartesian product G×Km
and a proper m-coloring of the vertices of G. Specifically,
we prove that every graph with
n vertices and maximum vertex degree
Δ
must have chromatic number χ(G) less
than or equal to Δ+1 and that the algorithm
will always find a proper m-coloring of the vertices of G
with m less than or equal to Δ+1. Furthermore,
we prove that this condition is the best possible in terms of n
and Δ by explicitly constructing graphs for
which the chromatic number is exactly
Δ+1. In
the special case when G is a connected simple graph and is neither
an odd cycle nor a complete graph, we show that the algorithm will always
find a proper m-coloring of the vertices of G with m
less than or equal to Δ. In the process, we
obtain a new constructive proof of Brooks' famous theorem of 1941. The
following proofs use two fundamental axioms: Euclid's Division Lemma [5]
and the Pigeonhole Principle [6].
Euclid's Division Lemma. Given a positive integer m and any integer n, there exist unique integers q and r with 0 ≤ r < m such that n = qm+r. Pigeonhole Principle. If l letters are distributed into p pigeonholes, then some pigeonhole receives at least ⌈l/p⌉ letters and some pigeonhole receives at most ⌊l/p⌋ letters. 5.1. Proposition. Given a simple graph G with n vertices, m colors and an initial independent set S of G×Km. At each stage of procedure 3.1, if there are l vertices outside S and the maximum degree among the vertices inside S is less than ⌈l/(nm−l)⌉, then procedure 3.1 produces a strictly larger independent set. Proof. By contradiction. Suppose the independent set S is maximal. Then there are no adjoinable vertices and every vertex outside S must have a neighbor inside S. Thus there are at least l edges (letters) with one end vertex outside S and the other end vertex inside S, there being exactly p = nm−l vertices inside S (pigeonholes). By the pigeonhole principle, some vertex inside S must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices inside S is less than ⌈l/p⌉. ☐ 5.2. Proposition. Given a simple graph G with n vertices, m colors and an independent set S of G×Km, procedure 3.1 always produces a maximal independent set of G×Km. Proof. Procedure 3.1 terminates only when there are no adjoinable vertices. By definition, the resulting independent set must be maximal. ☐ 5.3. Proposition. Given a simple graph G with n vertices, m colors and an initial maximal independent set S of G×Km. If there are t vertices outside the maximal independent set S and the maximum degree among the vertices inside S is less than ⌈2t/(nm−t)⌉, then there exists a vertex (u1, v1) outside S such that (u1, v1) has exactly one neighbor (u2, v2) inside S and procedure 3.2 produces a maximal independent set different from S and of size greater than or equal to the size of S. Proof. By contradiction. Note that since S is maximal, there are no adjoinable vertices and every vertex outside S has at least one neighbor inside S. Suppose every vertex outside S has more than one neighbor inside S. Then there are at least l = 2t edges (letters) with one end vertex outside S and the other end vertex inside S, there being exactly p = nm−t vertices inside S (pigeonholes). By the pigeonhole principle, some vertex inside S must receive at least ⌈l/p⌉ edges contradicting the hypothesis that the maximum degree among the vertices inside S is less than ⌈l/p⌉. Thus, there exists a vertex (u1, v1) outside S such that (u1, v1) has exactly one neighbor (u2, v2) inside S. Now since procedure 3.2 exchanges (u1, v1) and (u2, v2), an independent set different from S but of the same size as S is created. Note that in the process some vertices outside the independent set might have become adjoinable. Then, procedure 3.2 applies procedure 3.1 that produces a maximal independent set different from S and of size greater than or equal to the size of S. ☐ 5.4. Proposition. Given a simple graph G with n vertices and m colors. If G has maximum vertex degree Δ, then the algorithm always finds a maximal independent set in G×Kmof size at least ⌈nm/(Δ+m)⌉. Proof. Note that the maximum vertex degree of the Cartesian graph G×Km is Δ+m−1.Consider any one turn of part I in the algorithm. After t vertices have been adjoined from a total of nm, there are l = nm−t vertices outside the independent set S and the maximum degree among the vertices inside S is certainly less than or equal to Δ+m−1. By proposition 5.1, if Δ+m−1 is less than ⌈l/(nm−l)⌉ = ⌈(nm−t)/(nm−(nm−t))⌉ = ⌈(nm−t)/t⌉ = ⌈(nm/t)−1⌉, then a strictly larger independent set is produced by adjoining a vertex. Hence, as long as t is less than ⌈nm/(Δ+m−1+1)⌉ = ⌈nm/(Δ+m)⌉, a vertex can still be adjoined and procedure 1 continues. Thus, at least ⌈nm/(Δ+m)⌉ vertices are adjoined, producing an independent set of size at least ⌈nm/(Δ+m)⌉. By propositions 5.1, 5.2 and 5.3, all of the independent sets produced by the algorithm are maximal and of size at least ⌈nm/(Δ+m)⌉. ☐ 5.5. Proposition. Let G be a simple graph with n vertices and maximal vertex degree Δ. Given m colors where m is greater than or equal to Δ+1, the algorithm always finds a proper m-coloring of the vertices of G. Proof. We shall show that the size of any maximal independent set S found by the algorithm in the cartesian graph G×Km is at least n, by contradiction. Suppose the independent set S = {(u1, v1), (u2, v2), ..., (uk, vk)} is maximal and k is less than n. Note that u1, u2, ..., uk must be k distinct vertices of G since ui = uj implies that there is an edge between (ui, vi) and (uj, vj) in G×Km since Km is complete. Let u be a vertex of G different from u1, u2, ..., uk. Then, for each vertex v of Km, the vertex (u, v) of G×Km is outside S and must have a nieghbor in S since S is a maximal independent set. The only way the vertex (u, v) can have a neighbor (ui, vi) in S is if v = vi and u is a neighbor of ui in G. Thus the degree of the vertex u is greater than or equal to m in G. This contradicts the hypothesis that m is greater than or equal to Δ+1. ☐ 5.6. Corollary. For any simple graph G with maximal vertex degree Δ, the chromatic number χ(G) is less than or equal to Δ+1. Proof. By proposition 5.5, the algorithm always finds a proper m-coloring of the vertices of G for m equal to Δ+1. ☐ 5.7. Proposition. Given any positive integers n and Δ such that 0 < Δ < n, there exists a graph G with maximum vertex degree Δ and chromatic number χ(G) = Δ+1. For any such graph the algorithm always finds a proper m-coloring of the vertices of G for m equal to Δ+1. Proof. Let n = q(Δ+1)+r with 0 ≤ r < Δ+1 by Euclid's division lemma. There are two cases.
Proof. The proposition is trivial if n is less than 3, so assume that n is at least 3. Let m = Δ. First suppose that G is a simple path or an even cycle. Then m = Δ = 2 and the first turn of part I will find a maximal independent set S = {(u1, 1), (u2, 2), (u3, 1), (u4, 2), ..., (un-1, 1), (un, 2)} with alternating colors 1 and 2 such that the simple path or even cycle u1, u2, u3, u4, ..., un-1, un consists of all the vertices of G. Thus, if G is a simple path or an even cycle then the algorithm finds a proper 2-coloring of G. Since G cannot be an odd cycle by hypothesis, from now on let us assume that G is neither a simple path nor a cycle. Since G is not complete, there exist three vertices u', u'', u''' such that {u', u''}, {u'', u'''} are edges of G and {u', u'''} is not an edge of G. Let u1 = u' and v1 = 1. Let S = {(u1, v1), (u2, v2), ..., (uk, vk)} be the maximal independent set of G×Km generated by the turn of part I starting with (u1, v1) and suppose k is less than n. Note that u1, u2, ..., uk must be k distinct vertices of G since ui = uj implies that there is an edge between (ui, vi) and (uj, vj) in G×Km, since Km is complete.
or or or or 5.9. Corollary [Brooks' Theorem, 1941]. Let G be a simple graph with n vertices and maximal vertex degree Δ. If G is a connected and is neither an odd cycle nor a complete graph, then the chromatic number χ(G) is less than or equal to Δ. Proof. By proposition 5.8, the algorithm finds a proper m-coloring of G for some m less than or equal to Δ. ☐ 5.10. Question. For all known examples of graphs, the algorithm finds a proper m-coloring of the vertices of the graph G for m equal to the chromatic number χ(G). In view of the importance of the P versus NP question [3], we ask: does there exist a graph G for which this algorithm cannot find a proper m-coloring of the vertices of G with m equal to the chromatic number χ(G)? |
|
We demonstrate the algorithm with a C++
program following the style of [7]. The demonstration
program package [download] contains
a detailed help file and section 7 gives several examples of input/output
files for the program.
|
|
We demonstrate the algorithm by running
the program on several famous graphs, including a proper four-coloring
of the map of India and two large Mycielski benchmark graphs with hidden
minimum vertex colorings. In each case, the algorithm finds a proper
m-coloring
of the vertices of the graph G in polynomial-time with m
equal to the chromatic number χ(G).
7.1. The Tetrahedron [8]. We run the program
on the graph of the Tetrahedron with n = 4 vertices. The algorithm
finds a proper m-coloring of the vertices for m = χ(G)
= 4.
7.2. The Kuratowski Bipartite Graph K3, 3 [9].
We run the program on the Kuratowski bipartite graph
K3, 3
with n = 6 vertices. The algorithm finds a proper m-coloring
of the vertices for m = χ(G) =
2.
7.3. The Octahedron [8]. We run the program
on the graph of the Octahedron with n = 6 vertices. The algorithm
finds a proper m-coloring of the vertices for m = χ(G)
= 3.
7.4. The Bondy-Murty Graph G1 [4].
We run the program on the Bondy-Murty graph G1 with n
= 7 vertices. The algorithm finds a proper m-coloring of the vertices
for m = χ(G) = 4.
7.5. The Wheel Graph W8 [4].
We run the program on the Wheel graph W8 with n
= 8 vertices. The algorithm finds a proper m-coloring of the vertices
for m = χ(G) = 4.
7.6. The Cube [8]. We run the program on the
graph of the Cube with
n = 8 vertices. The algorithm finds a proper
m-coloring
of the vertices for m = χ(G) =
2.
7.7. The Petersen Graph [10]. We run the program
on the Petersen graph with n = 10 vertices. The algorithm finds
a proper
m-coloring of the vertices for m = χ(G)
= 3.
7.8. The Bondy-Murty graph G2 [4].
We run the program on the Bondy-Murty graph G2 with n
= 11 vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 3.
7.9. The Grötzsch Graph [11]. We run the
program on the Grötzsch graph with
n = 11 vertices. The algorithm
finds a proper
m-coloring of the vertices for m = χ(G)
= 4.
7.10. The Chvátal Graph [12]. We run
the program on the Chvátal graph with n = 12 vertices. The
algorithm finds a proper
m-coloring of the vertices for m
= χ(G) = 4.
7.11. The Icosahedron [8]. We run the program
on the graph of the Icosahedron with n = 12 vertices. The algorithm
finds a proper
m-coloring of the vertices for m = χ(G)
= 4.
7.12. The Bondy-Murty graph G3 [4].We
run the program on the Bondy-Murty graph G3 with n
= 14 vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 2.
7.13. The Bondy-Murty graph G4 [4].
We run the program on the Bondy-Murty graph G4 with n
= 16 vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 3.
7.14. The Ramsey Graph R(4,4) [6]. We
run the program on the Ramsey graph R(4,4) with n = 17 vertices.
The algorithm finds a proper
m-coloring of the vertices for m
= χ(G) = 6.
7.15. The Dodecahedron [8]. We run the program
on the graph of the Dodecahedron with n = 20 vertices. The algorithm
finds a proper
m-coloring of the vertices for m = χ(G)
= 3.
7.16. The Mycielski 5-Chromatic Graph [13].
We run the program on the Mycielski 5-chromatic graph with n = 23
vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 5.
7.17. The Grünbaum Graph [12]. We run the
program on the Grünbaum graph with n = 25 vertices. The algorithm
finds a proper
m-coloring of the vertices for m = χ(G)
= 4.
7.18. The Map of India [14]. The 30 states of
mainland India are shown below in Figure 7.18.1. We define the graph of
India as follows. There is a unique vertex inside each region defined by
a state. There is an edge connecting two distinct vertices if and only
if the two corresponding regions have a whole segment of their boundaries
in common. The graph of India is shown below in Figure 7.18.2. We run the
program on the graph of India with n = 30 vertices. The algorithm
finds a proper
m-coloring of the vertices for m = χ(G)
= 4, and correspondingly, a proper four-coloring of the map of India.
7.19. The Mycielski 6-Chromatic Graph [13].
We run the program on the Mycielski 6-chromatic graph with n = 47
vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 6.
7.20. The Mycielski 7-Chromatic Graph [13].
We run the program on the Mycielski 7-chromatic graph with n = 95
vertices. The algorithm finds a proper
m-coloring of the vertices
for m = χ(G) = 7.
|
| [1] | R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 1972. |
| [2] | R. Frucht, Graphs of degree three with a given abstract group, Canad. J. Math., 1949. |
| [3] | Stephen Cook, The P versus NP Problem, Official Problem Description, Millennium Problems, Clay Mathematics Institute, 2000. |
| [4] | J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier Science Publishing Co., Inc, 1976. |
| [5] | Euclid, Elements, circa 300 B.C. |
| [6] | F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc., 1930. |
| [7] | Stanley Lippman, Essential C++, Addison-Wesley, 2000. |
| [8] | Plato, Timaeaus, circa 350 B.C. |
| [9] | K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math., 1930. |
| [10] | J. Petersen, Die Theorie der regulären Graphen, Acta Math., 1891. |
| [11] | H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel, Z. Martin-Luther-Univ., 1958. |
| [12] | B. Grünbaum, A Problem in Graph Coloring, Amer. Math. Monthly, 1970. |
| [13] | J. Mycielski, Sur le coloriage des graphs, Colloq. Math., 1955. |
| [14] | Ashay Dharwadker, A New Proof of the Four Colour Theorem, http://www.dharwadker.org , 2000. |
| [15] | C. Berge, Graphes et Hypergraphes, Dunod, 1970. |
| [16] | Ashay Dharwadker, The Vertex Cover Algorithm, http://www.dharwadker.org/vertex_cover , 2006. |
| [17] | Ashay Dharwadker, The Independent Set Algorithm, http://www.dharwadker.org/independent_set , 2006. |
| [18] | Ashay Dharwadker, The Clique Algorithm, http://www.dharwadker.org/clique , 2006. |
|
Copyright © 2006 by Ashay Dharwadker. All rights reserved. |
