BOUNDS ON THE CHROMATIC NUMBER
by
Kim Mitchell
A thesis submitted to the
University of Colorado at Denver and Health Sciences Center
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
2007
This thesis for the Master of Science
degree by
Kim Mitchell
has been approved by
Date
Mitchell, Kimberly (M.S., Applied Mathematics)
Bounds on the Chromatic Number
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
The chromatic number of a graph is the least number of colors required to properly
color a graph. For many graphs, this number is difficult to find, so we look for upper
and lower bounds to help get an idea of what the chromatic number might be. First
general upper and lower bounds are discussed, including a number of well-known
results. Then Brooks Theorem is proved, giving an upper bound for most graphs. In
this section an improvement on Brooks Theorem is also discussed. Finally, Reeds
Conjecture is explored, in which an average of a lower and upper bound is thought to
be an upper bound.
This abstract accurately represent the content of the candidates thesis. I recommend
its publication.
Signed|
J. Richard Lundgren
TABLE OF CONTENTS
CHAPTER
1. INTRODUCTION............................................1
Definitions/Notations................................1
2. GENERAL LOWER BOUNDS OF THE CHROMATIC NUMBER............3
Clique number as lower bound.........................3
Perfect graphs.......................................8
3. GENERAL UPPER BOUNDS OF THE CHROMATIC NUMBER............14
Degree as an upper bound............................14
Welsh-Powell Theorem................................15
^-critical graphs...................................16
Szekeres-Wilf Theorem...............................17
Gallai, Roy, Vitaver Theorem........................17
Four color Theorem..................................20
Five color Theorem..................................23
4. BROOKS THEOREM AND IMPROVEMENTS.......................26
Brooks Theorem.....................................26
Improvement on Brooks Theorem......................31
5. REEDS CONJECTURE......................................47
Examples of specific graphs.........................48
IV
Classes of graphs.......................................51
Graphs with specific clique numbers.....................54
Summary.................................................55
REFERENCES..........................................................57
CHAPTER 1
INTRODUCTION
A ^-coloring of a graph G is a labeling of the vertices in G, f: V(G) - S, where
|S| = k. A ^-coloring is proper if all adjacent vertices in G have different labels. By
definition, a graph is ^-colorable if it has a proper ^-coloring. In this paper, a coloring
will always refer to a proper coloring. The chromatic number x{G) is the least k
such that G is ^-colorable.
Determining the chromatic number of any given graph is often difficult, however we
can come up with bounds that narrow the possibilities for the chromatic number.
Certain bounds may be good bounds (that is close to the actual chromatic number of
the graph) on some kinds of graphs, while not very good on others. With each bound,
we will examine examples of graphs in which a bound is good, or not veiy close to
the chromatic number at all. To come up with useful bounds, as well as prove these
bounds hold, we will need to use the following definitions.
The order of a graph (the number of vertices) will be denoted n{G). The vertex set
of a graph is V(G). The edge set of a graph is E(G). The clique number a>(G) of
a graph G is the largest set of mutually adjacent vertices in G. The degree of a vertex
v is the number of vertices that v is adjacent to, the maximum degree A(G) of a
graph G is the largest degree of all vertices in G, and the minimum degree S(G) of a
graph G is the smallest degree of all vertices in G. The independence number a(G)
of a graph G is the maximum size of an independent set of vertices (vertices that are
-1-
mutually non-adjacent). The connectivity k(G) of a graph G is the minimum size
of a vertex set S such that G S is disconnected or has only one vertex.
Clearly it does not make sense to color a graph that contains loops, as a vertex could
not be a different color than itself, so in this paper we assume all graphs are loopless.
However, multiple edges do not change a proper coloring of a graph, so in most cases
we do not care if we have multiple edges. For ease we will assume in this paper we
are dealing with simple graphs, that is graphs having no loops or multiple edges.
-2-
CHAPTER 2
GENERAL LOWER BOUNDS OF THE CHROMATIC NUMBER
Proposition 2.1; For every graph G, %(G) > eo(G).
Proof: Since all vertices in the clique of maximum degree are mutually
adjacent, they each must have a different color in a proper coloring.
There are several kinds of graphs for which this bound holds with equality. We will
look at a few such examples in the results below. However, there are graphs for
which this bound is not very good at all. For instance, the following Mycielski
construction produces a graph with a chromatic number that gets one bigger with
each iteration, and yet is still triangle free (so the clique number is only 2). [6]
The Mycielski construction produces a graph G from a graph G as follows. Begin
with a graph G with vertex set V(G) V and edge set E(G) = E. The Mycielski
graph G has vertex set V u V'u {w}, where V'={x':xeV}, and edge set
Eu{x'y: xy e E\j {x'u : x'e V'}. [1] If the original graph G is triangle free, G will
also be triangle free as no edges added in the graph create a triangle. If G has
chromatic number k, G will have chromatic number k + 1. This is true because each
vertex x can be colored the same color as vertex x, since it is connected only to the
neighbors of x, and not to x. However, since each vertex x is connected to the vertex
u, the final vertex must be colored a new color, so u will be colored the k + 1 color.
The second iteration of the Mycielski construction on K2 produces the 4-chromatic
Groetzsch graph, shown below.
-3-
Now we look to graphs where Proposition 2.1 holds with equality.
A complete graph is a simple graph whose vertices are pairwise adjacent, that is
every two vertices are connected (see picture below). We use the notation Kn to
denote a complete graph on n vertices. A complete graph will be our first example
where Proposition 2.1 holds with equality.
Proposition 2.2: For every complete graph Kn, %{Kn) = co(Kn).
Proof: A complete graph is a clique, and since every vertex is adjacent to
every other, %(K) = n(K) = co{Kn).
A bipartite graph is the union of two disjoint independent sets called partite sets
(see the left picture below). A complete bipartite graph, or biclique is a simple
bipartite graph such that two vertices are adjacent if and only if they are in different
-4-
partite sets (see the right picture below). We use the notation Kr s to denote a
biclique with partite sets of size r and s. Bipartite graphs are the second example
where Proposition 2.1 holds with equality.
Proposition 2.3; For every bipartite graph G, %(G) = co(G).
Proof: In a bipartite graph, the largest clique has size two. Each of the
independent sets can be colored in one color, since all the vertices in the set
are non-adjacent. So %(G) = oj(G) = 2.
In order to prove the next result, we will use the greedy coloring algorithm. The
greedy coloring algorithm takes an ordering of vertices vlv..,vn and colors vertices in
that order, assigning to each vertex the smallest-indexed color not already used by its
previously colored neighbors.
Proposition 2.4 is about interval graphs. An interval representation of a graph is an
assignment of an interval to a vertex of a graph,, such that two vertices are adjacent if
and only if the corresponding intervals intersect. A graph with such a representation
is called an interval graph (see picture below).
-5-
Proposition 2.4: For every interval graph G, j(G) = a>(G).
Proof: Take an interval graph G. Order the vertices of G according to left
endpoints of their corresponding intervals, then use the greedy coloring
algorithm. The size of the largest clique is the largest number of intervals that
intersect in the same place. Take the next vertex not in this clique. Then it
does not intersect in at least one of these intervals, and therefore can be
colored with the same color is the vertex representing that interval. Therefore,
the chromatic number will not exceed the size of the largest clique number.
In order to prove the next results, we will need the following definitions. A vertex of
G is simplicial if its neighborhood in G is a clique. A simplicial elimination
ordering is an ordering v,...,v, for deletion of vertices so that each vertex v, is a
simplicial vertex of the remaining graph induced by {vl5...,v,}. We will need a
preliminary result before we can prove Theorem 2.6.
Lemma 2.5 and Theorem 2.6 are about chordal graphs. A chordless cycle in G is a
cycle of length at least 4 in G that has no chord. A graph G is chordal if it is simple
and has no chordless cycle (see picture below).
-6-
Lemma 2.5 (Voloshin [19821): For every vertex x in a chordal graph G, there is a
simplicial vertex of G among the vertices farthest from x in G.
Proof: Let G be a chordal graph. We prove that G has a simplicial vertex by
induction on n(G). For (G) = 1, the one vertex in G is simplicial trivially.
Let n(G) > 2. Take a vertex x in G. If x is adjacent to all other vertices in G,
then we use the induction hypothesis on the graph G-x. Clearly any
induced subgraph of a chordal graph is chordal, because deleting vertices
cannot create chordless cycles. So assume G-x has at least one simplicial
vertex. Each simplicial vertex y of G-x is also simplicial in G, since x is
adjacent to all vertices in the neighborhood of y, as well as adjacent to y itself.
Now suppose x is not adjacent to every vertex in G. Let T be the set of all
vertices in G with maximum distance from x, and let H be a component of
G[T] (where G\f ] is the closed neighborhood of the vertices of T in G). Let
S be the set of vertices in G-T having neighbors in V(H), and let Q be the
component of G S containing S (see picture below).
We can show that S is a clique. Each vertex of S has a neighbor in V(H) and
a neighbor in Q. For distinct vertices u,v e S, the union of the shortest u, v-
paths through H and through Q is a cycle of at least 4. Since there are no
edges from V(H) to V(Q), this cycle has no chord other than uv. Since G
x
-7-
has no chordless cycle, clearly u and v must be adjacent. Since u,v e S were
chosen arbitrarily, S' is a clique. Now let G'= G[S u V(H)]; xgG1, so this
graph is smaller than G. Apply the induction hypothesis on G' and a vertex
ueS. Since S is a clique, S {} is contained in the neighborhood of u. So
the simplicial vertex z furthest from u is in V(H). Since the neighborhood of
z in G is contained in G', the vertex z is also simplicial in G, and z is a vertex
with maximum distance from x, proving the result.
Theorem 2.6(Beree 119601): For every chordal graph G, %(G) =
Proof: Let G be a chordal graph with x(G) = k. We know from Lemma 2.5
that every chordal graph has a simplicial vertex. We can get a simplicial
elimination ordering by induction on n(G) because every induced subgraph
of a chordal graph is still chordal. Let v,,...,vn be the reverse of the simplicial
elimination ordering. For each i, the neighbors of v( in {v,} form a
clique. We apply the greedy coloring algorithm with this ordering. If v,
receives color k, then colors appear on the earlier neighbors of v,.
Since they form a clique with v, we have a clique of size k. Thus we get a
clique whose size equals the chromatic number.
Propositions 2.2, 2.3, 2.4 and Theorem 2.6 are all examples of perfect graphs. A
perfect graph is a graph in which the chromatic number of every induced subgraph
equals the clique number of that subgraph. Some well-known perfect graphs are:
bipartite graphs, the line graphs of bipartite graphs, interval graphs, chordal graphs,
comparability graphs, wheel graphs with an odd number of vertices, Meyniel graphs,
split graphs and strongly perfect graphs. A line graph of a graph G, written L(G) is
the graph whose vertices are the edges of G, with ef e E(L(G)) when e = uv and
-8-
/ = vw in G. A transitive orientation of a graph G is an orientation D such that
whenever xy and yz are edges in D, there is also an edge xz in D. A graph G is a
comparability graph if it has a transitive orienatation. A wheel graph on w-vertices
is a vertex together with a cycle where every vertex of the cycle is adjacent to the
extra vertex (or the join of a vertex and a cycle, written Kx v Cn_x). A Meyniel
graph is a graph where every odd cycle has at least two chords. A split graph is a
graph which can be partitioned into a clique and an independent set. And finally a
strongly perfect graph is a graph in which every induced subgraph has an
independent set intersecting all its maximal cliques. [2]
Clearly in a perfect graph x(G) = __
subgraph. However, in 1974 Seinsche showed that more than just perfect graphs fit__
Proposition 2.1 with equality. He proved ;^(G) = co{G) for any graph which does not
have P4 as an induced subgraph. These graphs are also known as cographs or
complement reducible graphs. Theorem 2.8 is Seinsches proof of this result. First
we need Lemma 2.7 in order to prove Theorem 2.8. In this proof, we use the
following definition. The complement G of a graph G is the graph with vertex set
V(G) defined by uve E(G) if and only if uv E{G).
Lemma 2.7; Let G be a graph with a point set X. The following statements are
equivalent:
1. G has no induced subgraph isomorphic to P4.
2. Every subset of X with more than one element is not G-connected or not
G -connected.
Proof:
-9-
(2 => 1) Suppose G has an induced subgraph G' isomorphic to P4. Note that
G' is connected and the complement of G' is also isomorphic to P4. So the
point set of G' is both G-connected and G -coimected.
(1 => 2) Now suppose G has no induced subgraph isomorphic to P4.
Suppose there is a non-trivial subset of X which is both G-connected and G -
connected. Let X' be such a set with the smallest number of points possible,
and let x, g X'. X'-{x,} is not G-connected or not G -connected, since X' is
a minimum set. WLOG suppose X'-{xl} is not G-connected (switch G and
G if necessary). Therefore, {jc, } is G -connected, so there exists a point
jc2 g X'-{x{} adjacent to x, in G. The subgraph of G induced by X'-{x[}
has more than one component since it is not connected. Let X" be the point
set of the component that contains x2. X" and X'-{x, }-X" are both non-
empty and there is no line of G joining an element of X" and an element of
Since X' is G-connected, there must be points x3 g X" and
jc4 g X'-{xl}- X which are both adjacent to xl in G. Let S' be the set of all
elements of X" adjacent to x, in G and let S" be the set of all elements of
X" adjacent to x, in G. Clearly x2 g S' and x3 g S", so both sets are non-
empty. Since these are complementary subsets of the point set X", there
must be points x2'eS' and x3'g S" which are adjacent in G. So we now
have the following edges in G: x2'x3',x3'x1,x1x4 g E(G) and the following
edges in G: x,x2',x2,x4,x4x3'g E{G). Thus the subgraph induced by
{xj,x2',x3',x4} is isomorphic to P4 for both graphs G and G. This is a
contradiction, so there cannot exist a subset of X which is both G-connected
and G-connected.
-10-
Theorem 2.8 (Seinsche [19741): If a graph G has no induced subgraph isomorphic
to P4, then z(G) = co(G).
Proof: We prove this by induction. Clearly the theorem holds for a graph
with one point only. Let G be a graph with w(G) > 1 points, and assume the
theorem holds for all graphs with less than n(G) points. From Lemma 1.7 we
know the point set of G is either not G-connected or not G -connected.
If G is not connected consider the components C, of G. Clearly
%(G) = maxt x(Ct) and m(G) = max,
non-empty components of G, the point set of each C, is smaller than the point
set of G. Thus by the induction hypothesis, %(Ci) = co(Ci) for all C,, so
*(G) = a>(G).
If G is not connected, consider the complements of Ci5 where the s are
the components of G Since each of the vertices in a particular C, are now
connected to all the vertices in the other C, s, this gives us %(G) = ^(C,).
i
Likewise, since each vertex in a particular C, is connected to all the vertices
in the other C, s, this gives us co(G) -
i
least two non-empty components of G, the point set of each C, is smaller than
the point set of G. Thus by the induction hypothesis, j(Cj) =
C(,so *(G) = m(G).
Theorem 2.8 gives us the largest set of graphs for which Proposition 2.1 holds with
equality. However, as we saw this bound is not always useful, as in the Mycielski
construction that we observed earlier. So we look to find other bounds as well.
-11 -
Proposition 2.9: For every graph G, %(G) >
a(G)
Proof: Each color class in a graph G is clearly an independent set, since no
two vertices with the same color are adjacent, and so each color class has at
most a(G) vertices. So a(G) %(G) > n{G), and since a{G) is a positive
non-zero number, it can be divided on both sides of the inequality to give the
desired result.
Note that if G is a complete graph, the values in Propositions 2.1 and 2.9 are equal,
because a(G) -1 and n(G) = o)(G) in a complete graph. In a bipartite graph,
n{G)
1 < - < 2, and since we know /(G) = 2 for bipartite graphs, this bound is
a(G)
relatively tight. However, there are some graphs where this bound is not very useful.
For example, consider a graph with a large independent set, compared to the number
of vertices in the graph, together with a large clique (see the picture below). Say the
number of vertices in the clique and the independent set are the same. Then
= 2, but x(G) = which can be much bigger than 2.
a(G) 2
n(G)
vertices
2
n(G) .
vertices
2
-12-
So we have found two lower bounds on the chromatic number, sometimes with tight
results and sometimes not. Now we look to find some upper bounds on the chromatic
number.
-13-
CHAPTER 3
GENERAL UPPER BOUNDS OF THE CHROMATIC NUMBER
Many upper bounds come from algorithms that actually produce a coloring for a
particular graph. In order to prove the next result, we will again use the greedy
coloring algorithm.
Proposition 3.1: ;^(G) < A(G) +1
Proof: Let G be a graph with maximum degree A(G). In any vertex
ordering, each vertex has at most A(G) earlier neighbors, so the greedy
coloring would use at most A(G) +1 colors.
This bound holds with equality in two cases, as shown in the next result.
Proposition 3.2: j(G) = A(G) + 1 if G is a complete graph or an odd cycle.
Proof: First suppose G is a complete graph. So A(G) = n(G) -1, so
A(G) +1 = n{G). Since %(G) = n(G) in a complete graph, we get the result.
Now suppose G is an odd cycle, so A(G) = 2. All odd cycles have chromatic
number 3. So again, we get %(G) = A(G) +1.
Later we show that for any connected graph, this bound holds with equality in only
these two cases. However, again this upper bound is not always a tight upper bound.
For example, consider a star with a large number of vertices. A star is a bipartite
graph consisting of one vertex adjacent to all the others (see the picture below). The
- 14-
vertex adjacent to all others has degree n(G) -1, but since the graph is bipartite the
chromatic number is 2.
Proposition 3.3 fWelsh-Powell 19671: If a graph G has degree sequence
dl >... > dn, then /(G) < 1 + maXj min{^,i -l}.
Proof: Apply the greedy coloring to the vertices in non-increasing order of
degree, starting with dl and ending with dn (choosing any order for vertices
with the same degree). For the z'th vertex v,, it will have at most min{dt, / l}
earlier neighbors, so there are at most that many colors on all of its previous
neighbors. So at most the color of v, will be l + min{d,,/-l}. This is true
for each vertex, so altogether we need at most the maximum of this number
over i, thus we get the upper bound of 1 + max, min{*
This bound brings a big improvement on Proposition 3.2 for several graphs. For*
instance, in the example of the star above the vertex adjacent to all others would be
v,, and the other vertices in a random order. Since the degree of all the other vertices
is one, and min{z/,,/-l} for v, is one, 1 + max, min{d,, / l} = 2 yielding equality in
the Welsh-Powell inequality (whereas we had a huge gap between the bound and
chromatic number in the Proposition 3.2 inequality).
Proposition 3.4: For any graph G with m edges, /(G) < + J2m + .
2 V 4
-15-
Proof: Take a coloring of G that uses k = j(G) colors. We know G has at
least one edge between any two color classes because otherwise we could use
the same color for each of those classes. So m > i k(k -1). Solving this
inequality for k gives us the result. [9]
For the next result, we consider ^-critical graphs. A graph G is ^-critical graph if
Z(H) < x(G) = k for every proper subgraph H of G.
Lemma 3.5: If //is a ^-critical graph, then 8{H) > k -1.
Proof: Let x be a vertex of H. Because H is ^-critical, H-x is Z-l-
colorable. If the degree of x is less than k-1, then the k-\ colors used on
H x do not all appear in the neighborhood of x. Thus we could use a color
not used on the neighbors of x to obtain a k -1 -coloring of H. This is a
contradiction, since %(H) = k. So for each vertex, the degree must be at least
k-l,so S(H)>k-1.
Lemma 3.6: Every graph G with %(G) = k has a ^-critical subgraph H.
Proof: Take an optimal coloring of G. Find all the vertices colored the k-th
color. At least one vertex in this set must have k-1 neighbors, because
otherwise the graph would not require k colors. Take one such vertex x. Let
H be a subset of neighborhood of x, taking only one neighbor of x that is
colored each of the k 1 colors. If x is removed, then H-x is already
colored with k -1 colors. If another vertex is removed, then x can be colored
the color of the vertex removed, so it would also be k -1 -colorable. So H is
^-critical.
- 16-
If G is a graph, then
Theorem 3.7 (Szekeres-Wilf 119681):
Z(G)< l + maxcG 5(H).
Proof: Let k = z(G), and let H' be a ^-critical subgraph of G. Lemma 3.5
gives us %(G) -1 = z(H') -1 ~~
Theorem 3.8 (Gallai [19681, Roy 119671, Vitaver 119621): If D is an orientation of~~
a graph G with longest path length 1(D), then z(G) < 1 + l(D). Equality holds for
some orientation of G.
Proof:
(1) First we show z(G) ^ 1 + 1(D). Let D be an orientation of G. Let D' be
a maximal subdigraph of D that contains no cycle. Note that D' includes all
vertices of G. Color V(G) by letting the color of v be 1 plus the length of the
longest path in D' that ends at v. Let P be a path in Â£>', and let u be the first
vertex of P. Every path in D' ending at u has no other vertex on P, since D'
contains no cycle. So every path ending in u can be lengthened along P. This
means the color of vertices along each path in D' is strictly increasing. This
coloring uses 1 + /(D') on V(G). Now we check to see if this coloring is a
proper coloring. For each uv edge in D, there is a path in D' between its
endpoints, either the edge itself or another path in Â£>', which uv cant be
added to since it would create a cycle. So the colors on u and v are always
different, since colors are strictly increasing along paths in D'.
(2) Now we show z(G) = 1 + /(D) for some orientation of G. To do this, we
will construct an orientation D such that l(D*) < z(G) -1. Take an optimal
coloring of G. For each edge uv in G, orient it from u to v in D if and only
if the color of u is smaller than the color of v. Since we have a proper
-17-
coloring, this orients every edge in G. By construction, colors increase along
paths in D *, and there are only ^(G) colors, so /(Â£>*) < x(G) -1.
So this bound clearly is a good bound for an optimal choice of orientation of G.
However, such an orientation is not always easy to find, and choosing a bad
orientation can give a very loose bound. For instance, consider a cycle Cn for n
large. Pick an orientation by starting at any vertex and continuing in the same
direction around the circle, just making the final edge back to the original vertex
oriented in the opposite direction (so that no path will contain a cycle). The longest
path will be the edge set of the graph, without the final edge connecting the end of the
path back to the original vertex. The length of this path n 1, since the number of
edges in Cn is n. So the bound j(G) < 1 + 1(D) gives us j(G) < n, which is not
very useful.
On the other hand, if we had oriented the graph such that adjacent edges had opposite
orientations (which works for even cycles), or such that only one pair of adjacent
edges has the same orientation (which works for odd cycles), we can obtain a tight
bound from Theorem 3.8.
-18-
Even cycle
Odd cycle
We know in an even cycle /(G) = 2, and in an odd cycle /(G) = 3. In the even
cycle, the bound /(G) < 1 + /(Â£>) gives /(G) < 2 for the orientation above for even
cycles and /(G) < 3 for the orientation above for odd cycles.
Proposition 3.9: If G is a graph, then /(G) < n(G) a(G) +1.
Proof: Let S be a largest independent set of vertices, so |5| = a(G). Now
consider the graph H with vertex set V(G)-S. Since S is independent, the
entire set S can be colored with one color, so removing S from G will decrease
the chromatic number of G by one at the most. So /(//) > z(G) -1. On the
other hand, since \H\ = n-a(G), we clearly have x(H) M(G) (G).
Combining these two inequalities, we get /(G) -1 < /(//) < n(G) a(G), so
*(G)<(G)-a(G) + l. [3]
Now we look for bounds on specific kinds of graphs. We have already shown for
bipartite graphs, complete graphs, interval graphs and chordal graphs that
/(G) = (o(G). Lets look at planar graphs next. A graph is planar if it can be drawn
in the plane without crossing edges.
-19-
The coloring problem for planar graphs, or more commonly known as the map
coloring problem, has been studied extensively since 1852 when Francis Guthrie first
presented the problem. He was trying to color the map of counties of England, and
noticed that only four different colors were needed. He asked his professor, Augustus
De Morgan at University college about the problem De Morgan says A student of
mine [Guthrie] asked me today to give him a reason for a fact which I did not know
was a fact and do not yet. He says that if a figure be anyhow divided and the
compartment differently colored so that figures with any portion of common
boundary lines are differently colored four colors may be wanted, but not more -
the following is the case in which for colors are wanted. Query cannot a necessity for
five or more be invented...
In the subsequent years many proofs were given that turned out to be false. Alfred
Kempe gave a proof in 1879, and Peter Guthrie Tait gave a proof in 1880. In 1890
Percy Heawood showed Kempes proof was incorrect, and in 1891 Julius Petersen
showed Taits proof was incorrect. However, in 1890 Heawood was able to give a
proof that all planar graphs are five-colorable, a variation of which is shown in result
2.12. During the 1960s and 1970s German mathematician Heinrich Heesch
developed methods of applying the computer in order to search for a proof.
In 1976 Kenneth Appel and Wolfgang Haken from the University of Illinois proved
that planar graphs can be colored with at most four colors. They proved this by
computer, with algorithmic help from John Koch. Their proof was built on the fact
that if the four-color conjecture were false, there would be at least one map with the
smallest number of regions that requires five colors. Their proof showed that this
minimal counterexample could not exist. They used the following definitions in
order to do so. An unavoidable set is a set such that a minimal counterexample must
contain a member of it. A configuration is reducible if a planar graph containing it
-20-
cannot be a minimal counterexample. Appel and Haken found an unavoidable set of
reducible configurations, a contradiction, thus proving that a minimal counterexample
to the four-color conjecture could not exist. They reduced the infinite number of
maps to 1,936 reducible configurations which had to be checked one by one on the
computer.
Since Appel and Hakens proof, some improvements have been made. In 1996 Neil
Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas created a quadratic
time algorithm for 4-coloring planar maps. They found this by their new proof,
which used similar methods to Appel and Haken but required checking only 633
reducible configurations. Attempts are still being made to prove the theorem without
computers, but none have yet been verified.
There are also efficient algorithms to determine whether 1 or 2 colors are enough to
color a planar graph, or map. Determining whether 3 colors is enough is NP-
complete. Determining whether a general (possible non-planar) graph is 4-colorable
is also NP-complete. [12]
In order to prove Theorem 3.13, the five-color theorem, we need the following
definitions and preliminary results. A plane drawing of a planar graph G divides the
set of points in the plane not in V(G) into regions called faces (in the picture below
each number represents a face.
5
-21 -
Leonard Euler was the first one to discover the formula in Result 2.10, that in a
connected planar graph with n(G) vertices, e(G) edges, and / faces,
n(G) e(G) + f = 2. He first mentioned this result in a letter to Christin Goldbach in
1750, and later published two papers describing his work in detail and with the first
attempted proof. However, he did not give a correct proof of the formula. A French
mathematician, Adrian Marie Legendre gave the first correct proof using metrical
methods, a fairly different proof than the one given below.
Theorem 3.10 (Eulers formula 117581): If G is a connected planar graph with
n(G) vertices, e(G) edges, and/faces, then n(G) e(G) + f = 2.
Proof: Take a spanning tree T of the graph G. For a tree, e(G) = n(G) -1 and
since there are no cycles in a tree/= 1, so the result is true. Now we construct
G by adding edges to T. Each time we add an edge to a tree, we create a new
face. So/and e(G) increase by the same amount each time, thus the quantity
n(G)-e(G) + f remains unchanged. [1]
Lemma 3.11: If G is a connected planar graph with n(G) > 3 vertices and e(G)
edges, then e(G) < 3n(G) 6.
Proof: Consider a planar graph G with / faces. Since G has no loops or
multiple edges, the degree of each face is at least 3 (a face must be formed by
at least 3 edges). So 3/ < 2e(G), since an edge can be an edge of two
regions. Substituting from Eulers formula / = -n(G) + e(G) + 2, we get
- 3n(G) + 3e(G) + 6 < 2e(G) => e(G) < 3n(G) 6.
Lemma 3.12: If G is a planar graph, then G contains a vertex of degree 5 or less.
-22-
Proof: We prove this by contradiction. Suppose every vertex in G has degree
at least 6. From Lemma 3.11 we know e(G) < 3n(G) 6. The number of
edges in a graph is the sum of all the degrees of the vertices divided by two,
since two vertices create an edge. So if each vertex has degree at least six, the
S /
number of edges is e(G) > = 3n(G). Putting these two inequalities
together, we get 3n(G) < e(G) < 3n(G) 6, which is impossible. So not every
vertex in G can have degree at least 6.
Theorem 3.13 IHeawood 18901: If G is a planar graph, then j(G) < 5.
Proof: We prove this by induction on n{G). If G has 5 or fewer vertices,
clearly the inequality holds because we can color each vertex a different color.
Assume that any planar graph with less than n(G) vertices can be colored
with 5 or fewer colors. Let G be a connected planar graph with n(G) vertices.
From Lemma 3.11 we know there exists a vertex v of degree 5 or smaller.
Consider the graph H = G-v. By the induction hypothesis, assume H is
colored with 5 or less colors. Now we add v back in and try to color G with 5
colors. If v is only adjacent to vertices colored with four colors, then color v
the fifth color and the result is true. Now suppose v is adjacent to five
vertices, and they are all colored different colors. Consider two vertices
adjacent to v that are colored 1 and 2 that are not consecutive vertices around
v (see pictures below), call these vertices x, and x2. We need to consider if
these vertices are connected, so we check if there is a path from x, to x2 not
through vertex v. There are two possible cases.
Case 1: Suppose all the vertices colored 1 and 2 that are reachable from x,
are different from all the vertices colored 1 and 2 that are reachable from x2.
-23-
Then switch all the colors on vertices reachable from Xj that are colored 1 and
2, and thus x, is now colored with color 2. Now the vertex v is not adjacent to
any vertices colored with color 1, so it can be colored 1. Thus G is 5-
colorable. (See picture below).
Case 2: Suppose the vertices colored 1 and 2 reachable from x, are also
reachable from x2. So changing the colors of this path doesnt help. So
consider instead vertices x3 and x4 colored with colors 3 and 4 that are
adjacent to v. There can be no path between x3 and x4 because such a path
would cross the path between vertices x, and x2, a contradiction since the
graph is planar. Thus we can interchange the colors on either x3 or x4 and its
-24-
reachable vertices colored with color 3 and 4 (see picture below). Say we
interchange the xi colors, then v is no longer adjacent to a vertex colored with
color 3, so it can be colored with color 3. Therefore G is 5-colorable.
-25-
CHAPTER 4
BROOKS THEOREM AND IMPROVEMENTS
So we have a number of upper bounds and lower bounds for the chromatic number.
However, in many cases these bounds are far apart, so we look to improve them. In
1941, Brooks improved Proposition 3.1 as shown below.
First we will need the following definitions to prove Brooks Theorem. A cut vertex
of G is a vertex whose deletion increases the number of components in G. A block of
a graph G is a maximal connected subgraph of G that has no cut vertex. A leaf block
is a block that contains exactly one cut vertex of G.
Theorem 4.1 IBrooks 19411; If G is a connected graph other than a complete graph
or an odd cycle, then %(G) < A(G).
Proof: Let G be a connected graph, and let k = A(G). If k < 1, G is K2, a
complete graph. If k = 2, G is either a path or a cycle since G is connected. A
path is bipartite, and a cycle is either an odd cycle or an even cycle, which is
bipartite. So G is either an odd cycle or bipartite. If G is bipartite with
maximum degree 2, /(G) = 2 = A(G) and the bound holds. So assume
k> 3.
Suppose G is not ^-regular. So there exists a vertex vn with degree less than
A(G). Since G is connected, we can find a spanning tree of G from v,
labeling vertices in decreasing order along the spanning tree. Then use the
greedy coloring algorithm with the ordering vlv..,vn to color G. Each vertex
-26-
besides vn will have at most k-1 lower-indexed neighbors, since it always has
a neighbor in the spanning tree with a higher index. Since the degree of v is
less than k, the entire graph can be colored using at most k colors.
Now suppose G is ^-regular. First consider the case where G has a cut vertex
x. Let G' be a subgraph consisting of a component of G x together with its
edges to x. The degree of x in G' is less than k, so with the same method used
above we can color G' with at most k colors. Do the same thing on the other
component(s) of G-x, then permute the colors so that x has the same color
in both colorings. This gives us a coloring of the entire graph G of at most k
colors.
Now suppose G is ^-regular, and has no cut vertex, and is therefore 2-
connected. In any vertex ordering, the last vertex has k earlier neighbors since
G is ^-regular, but we can still produce the coloring if we can ensure that two
of the neighbors of the last vertex receive the same color.
Suppose that some vertex vn has neighbors v, and v2 that are nonadjacent to
each other, and Cj-{v,,v2} is connected. Index the vertices of Cr-{v,,v2}
with 3,..., such that labels increase on a path towards vn. Each vertex has at
most Â£-1 lower indexed neighbors. So the greedy coloring uses at most k-\
colors on neighbors of vn, since v, and v2 have the same colors. Thus the
graph G can be colored with at most k colors. Therefore we just need to show
that every 2-connected ^-regular graph with k >3 has such a triple of
vertices, v,, v2 and v.
Choose a vertex x. If k(G-x)>2, let v, be x and v2 be a vertex with
distance 2 from x. Such a vertex exists because G is regular and not a
complete graph. Let vn be a common neighbor to v, and v2.
-27-
If k(G x) = 1, let v = x. Since G has no cut vertex, x has a neighbor in
every leaf block of G-x. Neighbors v, and v2 of x in two such blocks are
nonadjacent. Also G {x, v,, v2} is connected, since blocks have no cut
vertices. Since k>3, vertex x has another neighbor, and G-{vl5v2} is
connected. So we use the ordering as noted above, indexing the vertices of
G {vj, v2} with 3,..., such that labels increase on a path towards vn and
finally coloring and v2 the same color. Thus G is Â£-1 colorable.
So Brooks Theorem shows that j(G) < A(G), with the exceptions of odd cycles and
complete graphs. Several attempts have been made to take this one step further, and
examine for what graphs %(G) < A(G) -1.
In 1977 Borodin and Kostachka showed that if A(G) > 7 and co(G) <
A (G)
2
then
%(G) < A(G) -1. We will follow the outline of their proof below. First we need the
following definitions. The girth of a graph G, denoted g(G) is the length of its
shortest cycle. A graph with no cycle has infinite girth. A graph G is called k-
degenerated if every induced subgraph G' of G contains a vertex of degree less than
k. ak (G) is the smallest number of ^-degenerated subgraphs which cover the vertices
of G. Clearly a, (G) = j(G). a2 (G) is known as the point arboricity of the graph
G. We can also easily see that ak (G) <
A(G)
k
+ 1.
We utilize the following lemmas provided by Borodin and Kastchka in [3].
-28-
Lemma 4.2: If o)(G) < A(G) and 3 < A(G) < 2k, then ak (G) <
MG)
k
Lemma 4.3: Let A(G)+1 = ^(A, +1), for A, being non-negative integers, and
<=i
n> 1. Then there exists a covering of the vertices of G by n subgraphs G, of the
graph G such that A(G,) < A,, \*
Lemma 4.4: Let ^ f (v) > A(v) for every v e V(G). Then there exists a coloring*
16/
c :V(G) i-> 1 such that every vertex v is adjacent with fewer than /c(v)(v) vertices
colored by c(v).
These lemmas lead us to the following theorem, from which we will get our result as
a corollary.
Theorem 4.5: Let A{G) > 3 and k > 1. Then ak (G) <
( 1 A (G)-- A(G) +1
Lv k L t +1
+ 1 j
where t = max{3,2k, \p{G)Ik\-k}.
A(G) +1
Proof: Let s =
r + 1
and r = A(G) +1 s(t +1). Then
A(G) +1 = sit +1) + r and by Lemma 4.3, the vertices of G can be covered by
5 + 1 subgraphs G,,G2.,...,Gi+1 which have
[t, if 1 < i < s
A(G,)< i ... ^
|r -1, if z = s +1
By Lemma 4.2, using 0){G)
-29-
f[7/fc"l ifl
ak(G,)
|l + [_(r -1) / k J, if / = s +1
Thus
a,4(G,)
;=1
V A(G) +1 A(G)-(t + l)-L(A(G) + l)/ + l)J
k / + 1 k
A(G) (f + \ > )fA(G)+n
k l k k Jl 1 + 1 J.
+ 1
+ 1
l k * J
= since is an integer, so this completes our proof.
k k
Corollary 4.6: If A(G) > 7 and a>(G) <
A(G)-1
2
, then x(G) < A(G).
[3]
So Borodin and Kostachka have handled sets that are not that dense, but what about
the dense sets? In 1999 Bruce Reed addressed this situation. He showed that a graph
with sufficiently large A and no cliques of size A has a A -1 coloring. We follow
his outline to this result below. First we need to utilize several results proved by
Reed in [3], which will not be proved here.
Lemma 4.7: There is a positive constant e such that if A>3, then
X(G)<(\-e)(A(G) + l) + sco(G).
Lemma 4.8: For every b there is a Ah such that if A(G) > Ab and
co(G) < (A(G) +1)- 2b, then %(G) < (A(G) +1 )-b.
-30-
We will follow Reeds proofs of the several results below to provide the final proof of
the following result:
Theorem 4.9: There is a A0 such that if A(G) > Ac and
Z(G) < A(G) -1. In fact, A0 = 1014 will do.
Originally Borodin and Kostochka conjectured in [3] that A0 = 9 would be enough to
prove Theorem 4.9. However, they were unable to do so. We will attempt to use this
A0 for as much of the proofs as possible, to see if this is indeed the case.
The main idea of proving Theorem 4.9 is that if G is a minimal counterexample to the
result, then any reasonably dense set of about A(G) vertices is either a clique or the
intersection of two cliques. The first result we need in order to prove Theorem 4.9 is
that if G is a minimal counter-example to Theorem 4.9 of maximum degree A(G),
then its A(G) -1 cliques are disjoint. To do this, we will need to assume A(G) > 9 in
each of the following proofs. We start with these preliminary results:
Lemma 4.10: No two intersecting A(G) -1 cliques intersect in fewer than A(G) 3
vertices.
Proof: Suppose two A(G) -1 cliques intersect in A(G) k vertices. Then a
vertex in the intersection has
A(G)-2 + A(G)-2-(A(G)-k-1) = A(G) + k-3 neighbors in their union.
Since A(G) is the maximum degree of all vertices in G, k < 3. So the
intersection has at least A(G) 3 vertices.
Lemma 4.11: No two A(G) -1 cliques intersect in A(G) 3 vertices.
-31 -
Proof: Suppose there are two A(G) -1 cliques which intersect in a A(G) 3
clique, C. Let a, b, c, d be the other four vertices in the union of these two
cliques that are not in C. Note that each of these four vertices is adjacent to
every element of C. There is no triangle in the graph F induced by a, b, c, d,
because otherwise this triangle along with C would form a A(G) clique, a
contradiction since we started with A(G) -1 cliques. Thus F is bipartite and
has maximum degree two. So we can partition a, b, c, d into two pairs of non-
adjacent vertices. WLOG assume that ab and cd are not edges in G.
Since G is a minimal counterexample, we know that
H = G-C-a-b-c-d has a A(G)-1 coloring. We fix such a coloring,
and extend it to a coloring of G. First note that any vertex in G-H has at
most 2 neighbors in H because it is in a A(G)-1 clique in G-H and has
maximum degree A(G). So we can choose some color / which does not
appear on any of the at most four vertices of H which are incident to at least
one of a or b and assign this color to both a and b (since ab is not an edge in
G). Likewise we choose another color different from i to color both c and d.
Since we are assuming A(G) > 9, and we have at least two A(G) -1 cliques
we know there are at least 8 colors, so we have enough from which to choose
from. So now we have a A(G)-1 coloring for G-C. We extend this to a
coloring on G using the greedy coloring algorithm. Each vertex of C is
adjacent to all four of a, b, c, d, which only use two colors. Since each vertex
has A(G)-1 neighbors, the greedy algorithm will not require more than
A(G) -1 colors to color C. Therefore, j(G) = A(G) -1, a contradiction since
G is a counterexample of Theorem 4.9.
Lemma 4.12: No two A(G) -1 cliques intersect in A(G) 2 vertices.
-32-
Proof: Suppose there are two A(G) -1 cliques which intersect in a A(G) 2
clique C. Let x and y be the two other vertices in the intersecting cliques, not
in C. Note that x and y are not adjacent, because then combing them with C
we would obtain a A(G) clique.
Case 1: Suppose no vertex of C is adjacent to any of H = G-C-x-y. As
we did in Result 3.6, we find a coloring of H and extend it to a coloring of
G-C by coloringx andy the same color (since they are not adjacent). Since
each vertex of C has at most A(G) -1 neighbors and is adjacent to both x and
y, we can extend this coloring to a A(G)-1 coloring of G. This is a
contradiction since G is a counterexample of Theorem 4.9.
Case 2: Now assume there is a vertex z of H = G-C-x-y adjacent to a
vertex in C. If z is adjacent to all of C, then since G has no A(G) cliques it is
not adjacent to x and y. In this case we can color H z with A(G) -1 colors
(again, since G is a minimal counterexample we know such a coloring exists)
and extend this to a A(G)-1 coloring of G-C by coloring x, y, and z the
same color. Since each of these three vertices has A(G) 2 neighbors in C,
each has at most two neighbors in H-z, and since we are assuming that
A (G) > 9, we know there are eight colors available to use. Therefore, we can
find this A(G)-1 coloring of G-C. Now we use the greedy coloring
algorithm to extend this coloring to all of G. Since vertices in C are adjacent
to x, y, and z which are all the same color, this will produce a A(G) -1
coloring for G. Again, this is a contradiction since G is a counterexample of
Theorem 4.9.
Case 3: Now assume that z is not adjacent to all of C. Suppose z is not
adjacent to some vertex w in C. Since w is adjacent to all of C + x + y-w it
has at most one neighbor in H. Suppose z has at least three neighbors in C.
-33-
We take a A(G) -1 coloring of H z, and try to extend it to a coloring for all
of G. First we color z and w with the same color, since they are not adjacent.
Since z has at least three neighbors in C, it has at most A(G) 3 neighbors in
H -z. We already noted w has at most one neighbor in H, so there are still
two colors to choose from to extend the coloring to a A(G)-1 coloring of
H + w. Note that x and y have A(G) 2 neighbors in C, and therefore each
have at most two neighbors in H. Color x and y a color different from these
four neighbors, and also different from the color used for w and z (this is
possible since we had two choices for the color of w and z). So we have
extended this coloring to a A(G)-1 coloring of G-C + w. We use the
greedy coloring algorithm to color the rest of G, saving a neighbor of z, call
this vertex v, to color last. As we color C-w-v, there is always one
uncolored neighbor of the vertex and two neighbors, x and y, with the same
color. Therefore, we will only use A(G) -1 colors. Finally, we need to color
v. We know v is adjacent to w, x, y and z, but these four vertices only use two
colors so we can color v with one of the colors in the A(G)-1 coloring.
Therefore, we have extended our A(G)-1 to all of G. Again, this is a
contradiction since G is a counterexample of Theorem 4.9.
Case 4: Assume that z has at most two neighbors in C. If any non-neighbor w
of z does not have a neighbor in H, then color w and z the same color, and
proceed as we did in case 3. So we start with a A(G)-1 coloring of H-z,
color x and y the same color (but one different than the one we choose for w
and z). This is possible since z has one or two neighbors in C that are not
colored, and w has no neighbors that are colored, so there exists a color for
them. Again we use the greedy coloring algorithm on the rest of C, saving a
neighbor of z for the end, and then color that neighbor last because it has four
-34-
neighbors only using two colors. So we obtain a A(G) -1 coloring of G, a
contradiction since G is a counterexample of Theorem 4.9.
Case 5: Assume that z has at most two neighbors in C and that every non-
neighbor w in C of z has a neighbor in H (we know that w only has one such
neighbor since it has A (G) -1 neighbors in G H = C + x + y). In this case
we would like to show that there is some vertex w, as stated above, such that
the graph H^ obtained from H by adding an edge from z to the neighbor of
w, call it u, in H contains no A(G) clique. Note that if does contain a
A(G) clique, then NH (z) contains a A(G)-2 clique, since removing the
edge zu removes one vertex from the A(G) clique, and NH(z) does not
include z. Call this A(G) 2 clique D. The neighbor of z in H, call it u, is
adjacent to all of D. If NH (z) contains a A(G) 2 clique, we know that each
vertex in this clique has at most two neighbors outside of the clique in G.
Thus there are at most two vertices of H -z-NH (z) which are adjacent to at
least A(G) 2 vertices of NH (z). Each of these vertices has at most two
neighbors in C by assumption, so there are at most four vertices w in C not
adjacent to z for which H^ is a A(G) clique. Since A(G) > 9, we know that
C contains at least seven vertices, and at most two of them are adjacent to z.
Thus we can choose some vertex in C that is not adjacent to z such that H^
contains no A(G) clique. Now, note that A(//w) < A(g) since z has a
neighbor in C and u is adjacent to w. Since G is a minimal counterexample,
we can color Hm with A(G) -1 colors. Now when we remove die edge zu,
we can color H + w with A(G) -1 colors by letting z and w have the same
colors (since z and u would have had different colors in the original coloring,
and the only neighbor of w in H is u). Again we color as we did in case 3 by
-35-
coloring x and y the same color, saving some neighbor of z to color last, using
the greedy coloring algorithm and finally coloring z since it has four neighbors
using two colors. This produces a A(G)-1 coloring of G, a contradiction
since G is a counterexample of Theorem 4.9.
Lemmas 4.10,4.11, and 4.12 combine to give us the following:
Lemma 4.13: If G is a minimal counterexample to Theorem 4.9, then its A(G) -1
cliques are disjoint.
Proof: In Lemmas 4.10, 4.11, and 4.12 we showed that the only possibility
for the intersection of two A(G)-1 cliques is for them to intersect in
A(G) -1 points. Therefore, they are the same clique. So any two distinct
A(G) -1 cliques cannot intersect.
We can strengthen this result to give us the following:
Lemma 4.14: If G is a minimal counterexample to Theorem 4.9 of maximum degree
A (G), and K is a A(G) -1 clique of G then no vertex of G-K is adjacent to more
than four vertices of K. Furthermore, at most four vertices of K have degree
A(G) -1.
Proof: Suppose there is a A(G) -1 clique K and a vertex not in K which has
at least five neighbors in K. Let x be a vertex of G-K that has the maximum
number of neighbors in K. Note that the most neighbors jc could have in AT is
A(G) 3 because if it had at least A(G) 2 neighbors, this would form a
A(G)-1 clique that intersected K in A(G)-2 vertices, which we showed
-36-
was impossible in Lemma 4.12. Let y be a vertex in K not adjacent to x. Let
C K y and D = Nc (x).
Case 1: Suppose no vertex of D is adjacent to any of G C x y. Then
each vertex in D has degree A(G) -1 because it is in the A(G) -1 clique, and
is adjacent to x. Since G is a minimum counterexample, we can color
H-G-C-x-y with A(G)-1 colors. We can extend this to a coloring of
G-C by coloring x and y the same color, and since they both have neighbors
in C that are not yet colored, we still get a A(G)-1 coloring. We can then
extend this to a coloring on G-D since each vertex in C-D has two
neighbors in D which are not yet colored. Since each vertex in D has degree
A(G) -1, and is adjacent to both x and y which are the same color, we can use
the greedy coloring algorithm to complete a A(G) -1 coloring for all of G.
This is a contradiction since G is a counterexample to Theorem 4.9.
Case 2: Now suppose there is a vertex zin H = G-C-x-y that is adjacent
to a vertex in D. Suppose z is adjacent to four or more vertices of D. Since G
is a minimum counterexample, we can color H-z with A(G)-1 colors.
Choose a vertex w in C that is not adjacent to z other than y. Color the
vertices w and z the same color. Such a color exists in the A(G) -1 coloring
because z has at most A(G)-4 neighbors in H and w has at most two
neighbors in H. So that leaves us one color to use for w and z. Next color x
and y the same color, but something different than we used for w and z. This
is possible since together x and y have at most A(G) 3 neighbors combined
in H. Next we color all of C-D since each vertex again has 2 vertices in D
which have not been colored. Last we color D, saving a neighbor v of z for
last. Each vertex in D is adjacent to v which is uncolored, and is adjacent to
both x and y which have the same color. So we still get a A(G) -1 coloring.
-37-
Finally, v is adjacent to the four vertices w,x,y, and z which only use two
colors so we can extend the A(G)-1 coloring to all of G. This is a
contradiction since G is a counterexample to Theorem 4.9.
Case 3: Suppose that z is adjacent to at most three vertices of D. Since x has
at least five neighbors in K we know that there is a vertex w in D that is not
adjacent to z. If w has a neighbor u in H, then let H'= H + zu. If not, let
H'-H. By our proof of Result 3.7 we know that H' contains no A(G)
clique. We also know A (FT) < A (G) because z and u both have neighbors in
C, outside of H so adding one two their degree does not change the maximum
degree in H'. So since G is a minimal counterexample, we can find a
A(G)-1 coloring of H'. Extend this to a coloring on H + w by coloring z
and w the same color. As in case 2, we extend this by coloring x and y the
same color and saving a neighbor v of z to color last. This gives a A(G) -1
coloring for all of G, a contradiction since G is a counterexample to Theorem
4.9.
So x cannot have at least five neighbors in K, showing that no vertex of
G-K is adjacent to more than four vertices of K. To show the last part of
the result, suppose there is some A(G) -1 clique C in G containing a set S of
five vertices each with degree A(G) -1. Let v be one such vertex, and let z be
a neighbor of v not in C. By the first part of this result, we showed that z has
at most four neighbors in C. So there is at least one vertex w in S that is not
adjacent to z. Again, we can find a A(G) -1 coloring of G-C + w where w
and z have the same color and extend that to a coloring of G by saving v as the
last vertex colored. This would give us a A(G) -1 coloring for all of G, a
contradiction. Therefore at most four vertices of K have degree A(G) -1.
-38-
Lemma 4.15; If G is a minimal counterexample to Theorem 4.9, and H is a subgraph
7 3
of G with at most A(G) vertices such that every vertex of H has at least A(G)
6 4
neighbors in H then H is either a clique or consists of a clique CH with less than
A(G) -1 vertices together with a vertex vH.
Proof: Let G be a minimal counterexample to Theorem 4.9 and H be a set
7
with at most A(G) vertices which induces a graph of minimum degree
6
-A(G). We know for each pair of vertices there must be at least
1 7
-A(G) vertices in the set Sxy = N{x) n N(y) n H. Note that A(G)
3 6
vertices total minus A(G) for each vertex degree is A(G) so there must
be at least that many vertices in the intersection.
Case 1: Suppose H has 4 disjoint pairs of nonadjacent vertices
{(*i, yx),..., (x4 )}. Then there must be at least A(G) > 6 vertices which
are in two of the St v. In other words, H contains two vertices a and b such
that N(a) n N(b) n H contains two disjoint pairs of nonadjacent vertices, call
them (x, y) and (w,v). Since G is a minimal counterexample, we can color
G-H with A(G)-1 colors. We extend this to a coloring on
G-H + x + y + w + v by using the same color on each pair (one color for
(x,.y) and another for (w,v)). We know there are color available in the
3
original coloring because the degree of each vertex in H is at least A(G) and
since A(G) > 9 there are at least 6 vertices in //that each vertex is adjacent to,
thus using two colors for the four vertices leaves plenty of choices of the
-39-
original A(G)-1 colors. Let S = a+ b + (N(a)nN(b)nH)-v-w-x-y.
First we color the vertices in G S that have at most one neighbor in S and
then we will color vertices with at least two neighbors in S (we will call this
set 7). We noted earlier that N(a)r\N(b)nH has at least ^A(G) vertices,
so |Sj > ^ A(G) 2. If |s| < A(G) -1 then each vertex of S is adjacent to at
least A(G) + 2 vertices of H-S, because the degree of each vertex in H is
|A(G).
4
Furthermore, this means there are at least
f\ Yl ^
-A(G)-2 -A(G) + 2
3 A 4
= -----+ A(G) edges, and it will be useful to
12 6
use the fact that this is at least from S to H-S. Since |S| < A(G),
we find |r|>-A(G). So |5ur|>-A(G)-2. We see that if
6 2
> A(G) -1, the previous inequality holds as well, so it is true in any case.
So each vertex of H-S-T has at least two neighbors in S + T. So we can
extend our original coloring to each vertex G-S with at most one neighbor
in S using the original A(G) -1 colors. Each vertex in T has two neighbors in
S, so we extend our A(G)-1 coloring to all of G-S. The vertices in
S-a-b are adjacent to both a and b, so we can extend our coloring to them
as well. And finally we color a and b. Each of these vertices are adjacent to
the four vertices v, w,x,y, which only used two colors total. So we do not
need a new color for a and b. Thus we have extended our A(G) -1 to all of
G, a contradiction since G is a minimal counterexample to Theorem 4.9.
-40-
Case 2: Now assume H has no 4 disjoint pairs of nonadjacent vertices. Let
CH be the clique obtained by deleting a maximum number of disjoint pairs of
nonadjacent vertices in H. Clearly we can see that H-CH has at most six
vertices. If H CH has at least two vertices, then since CH was obtained by
deleting the maximum number of disjoint pairs, we know H either has two
pairs of nonadjacent vertices, or an independent set of three vertices. Either
way, there are four vertices in //which require only two colors (call this set of
four vertices X). We can choose two of these vertices to be from CH. Again,
we take a A(G)-1 coloring of G-H. We extend this by first coloring the
four vertices mentioned above with two colors. Then color H-CH. Since
each of these vertices are disjoint nonadjacent pairs, we can color with our
original A(G)-1 colors. Finally we color all of CH, saving two of the
vertices that are adjacent to all of X for last. Since CH is a clique and we are
saving two of the vertices for last, the rest will be A(G) -1 colorable. The
last two vertices are adjacent to the four vertices in X that together use two
colors. Therefore we can extend our A(G) -1 coloring to all of G. This is a
contradiction since G is a counterexample to Theorem 4.9.
From now on we will assume G is a counterexample to Theorem 4.9. with maximum
degree A(G) and V is the set of maximal cliques of G which contain at least
3
A(G) +1 vertices. Note that every vertex in G has degree A(G) or A(G) -1.
4
Lemma 4.16: If two elements C, and C2 of V with |C,|<|C2| intersect, then
|C,-C!|<1.
-41 -
Proof: Let x be a vertex in the intersection of the two cliques C, and C2.
Since the maximum degree of each vertex is A(G), we know that there are at
most A(G) vertices adjacent to x between the two cliques, so the union of C,
and C2 contains at most A(G) + 1 vertices. So we can use Lemma 4.15,
letting H be the union of C, and C2. So H is either a clique or a clique and a
vertex. Since C, and C2 are both maximal cliques, this mean either C, is
contained entirely in C2 or has one extra vertex not in C2.
Lemma 4.17: No element of XT intersects two other elements of XT.
Proof: Let x be a vertex in the intersection of all three elements of XT. By
Lemma 4.16 we know that the three elements have a common intersection.
Since each element is a clique, x is adjacent to all other vertices in the union
of the three elements. So there are at most A(G) +1 vertices in the union. Let
H be the union, and again use Lemma 4.15. If H is a clique, then each
element was not a maximal clique, a contradiction. H cannot be a clique plus
one vertex, because that vertex along with the other in the intersection all
originally came from cliques, so it would have to be adjacent to all the other
vertices. Therefore there is not vertex in the intersection of three elements of
r.
This result means we can partition the vertices of G into sets Sx,...,St where
/ = n(G) U{C|C e Xj}. Each S, is either a clique C( of XT or a clique C, of XT and a
3
vertex v, of G C, where v, is adjacent to at least A(G) of C,.
-42-
Lemma 4.18: If v is a vertex in some C, such that |C,| = A(G) p then there is at
most one neighbor of v not in C, that is adjacent to more than p + 3 vertices of C,.
Furthermore, if v has degree A(G) -1 there are no such neighbors.
Proof: Suppose there are two such neighbors of v, call them x and y that are
adjacent to more than p + 3 vertices of C,. Since G is a minimal
counterexample, we can color G C, -x-y with A(G)-1 colors. By
Lemmas 4.16 and 4.17 we know there must exist distinct vertices w and z in
C, such that w is not adjacent to x and z is not adjacent to y. We extend this
coloring by letting w and x have the same color, and y and z have the same
color (different than that used for w and x). Since w and z are in C, which are
not yet colored, there is a color in the A(G) -1 coloring that we can use, and
since x and y have more than p + 3 neighbors in C, they also have colors
available. Now extend the coloring to Ct-w-z, saving v and some
neighbor of x for last. Since each of these vertices has at least two uncolored
neighbors, this still produces a A(G) -1 coloring. The neighbor of x is also
adjacent to w, since both are in the clique C,, which are both colored the same
color. Since v is not yet colored, this is a color available for this vertex.
Finally, v is adjacent to w,x,y,z which only use two colors, so we can extend
the A(G) -1 coloring to all of G. This is a contradiction since G is a minimal
counterexample to Theorem 4.9, so there is at most one such neighbor as
stated above.
If v has degree A(G) -1 we use a similar argument. Let x be a neighbor of v
in G-C, with at least p + 3 neighbors in C,. First color G-Ct-x with
A(G) -1 colors, then extend this by coloring x and w the same color for some
vertex w in Ct that is not adjacent to x. Again, extend the coloring to C, w,
-43-
saving v and some neighbor of x for last. The neighbor of x is adjacent to both
x and w, which are colored the same color and v which is not yet colored.
Finally v is adjacent to x and w and has degree A(G) -1, so we extend the
A(G) -1 coloring to all of G. This is again a contradiction, so no such vertex
of degree A(G) -1 exists.
Lemma 4.19: For any C,, if |Ci| = A(G)-/> then we can find at least ^A(G)
disjoint triples each of which consists of a vertex v of C, and two neighbors of v
outside of C, both of which have at most p + 3 neighbors in Ct.
Proof: Take a maximal such set of triples, suppose it has k elements. Let S be
the set of 2k vertices outside C, contained in one of these triples. Let T be the
set of k vertices of C, contained in some triple. Since G has minimum degree
at least A(G)-1, the maximality of the triple set and Result 3.13 imply that
each vertex of Ci-T has at least p-1 neighbors in S. Thus there are at least
(p-lXA(G)-k) edges betweenSand Ct-T. On the other hand there are at
most 2k{p + 3) such edges. So if p is at least 2, then the desired result holds.
If p = 1, then the result holds by Theorem 4.9 because all but four of the
vertices of C, are adjacent to at least two vertices of G C,, each of which
has degree at most four in So we can actually find a disjoint set of size
A(G) 4
7
Lemma 4.20: If v is a vertex whose neighborhood contains fewer than
(G))2 ~ A(G) pairs of nonadjacent vertices then it is in some C;.
-44-
Proof: If v is not in any C,, then by Lemma 4.15 there is some vertex v0 in
3
the neighborhood of v, Na(y) which is adjacent to less than -A(G)-1
4
vertices in NG(v). We can also see there is a sequence v0,...,v of
vertices of G such that v, is adjacent to less than A(G) vertices of
Lemma 4.21: Any partial A(G) -1 coloring of G satisfying the three following
conditions can be extended to a A(G) -1 coloring of G.
(i) For every vertex v e L there are at least 2 colors appearing twice in the
neighborhood of v.
(ii) For each near clique St, there are two uncolored neighbors of v, in C,
(iii) For every C, there are two uncolored vertices w, and x, of C, whose
neighborhoods contain two repeated colors.
Proof: Color the uncolored vertices one at a time. If St is a near-clique, then
we color v, before coloring any of Ct, condition (ii) ensures this is possible.
For any S,, we color w( and x, after all of the rest of C,. We can color
C, w, xt because all the vertices in this set are adjacent to both w, and x,.
By condition (iii) we can color wt and x,. We can then color the vertices of L
because of condition (i).
So now we wish to find a partial A(G) -1 coloring satisfying the conditions of
Lemma 4.21. The last details that lead to the proof of Theorem 4.9 are proved by the
probabilistic method. See [9] for the proof details. Using the lemmas provided
^w-{v,|y<4
-45-
above, Reed shows that such a partial A(G) -1 coloring is possible to find if
A(G)>A0, where A0 =1014. Thus by Lemma 4.21 we extend this to a A(G)-1
coloring for all of G. Reed concludes his argument with some interesting comments.
He says with slight modifications to his proof, it is possible to use A0 = 10s. He also
is certain that the same proof can be used to narrow this down to A0 = 106. He thinks
the same method could work all the way down to Aa =1000, but that his method
could not do any better than A0 = 100. This would obviously be a huge improvement
on the initial Aa = 1014 value used, and we look forward to seeing his work in the
future to see how much improvement he can get on A0.
The original Borodin-Kostachka conjecture that A0 = 9 would do is obviously
stronger than any of these, and Reed expects that some other method could be used to
show this is true. Either way though, it seems clear that Brooks Theorem can be
improved upon for many graphs, and since no counter-examples have been obtained
for the Borodin-Kostachka conjecture, I also think it is likely that a proof will be
found for it eventually.
-46-
CHAPTER 5
REEDS CONJECTURE
We showed in Proposition 2.1 that %(G) > co(G), and in Proposition 3.1
%(G) < A(G) +1. These upper and lower bounds were fairly simple to prove, and
give us a range in which %(G) must be. However, in 1995 Bruce Reed conjectured
that we can combine the bounds into a new more restrictive inequality. In [2] he
conjectured that for any graph G, %(G) <
A(G) + l + o>(G)
2
This would be a very
powerful result, giving a new upper bound that is the ceiling of the average of an
upper and lower bound. If z(G) and A(G) + 1 are far apart, this could prove a vast
improvement to Brooks Theorem.
First we will examine some typical examples and check that Reeds conjecture holds,
then we will prove this conjecture for some basic graphs, and last we will move on to
some more difficult kinds of graphs and present the cases in which Reed proved the
conjecture true.
The first example we will look at is the Peterson graph. It is named after Danish
mathematician Julius Peterson, who used this graph in a paper in 1898. It is a 3-
regular graph with 10 vertices and 15 edges constructed in the following way: the
vertices are the 2-element subsets of a 5-element set and the edges are the pairs of
disjoint 2-element set (see the picture below).
-47-
12
Proposition 5.1: Reeds Conjecture holds for the Peterson graph.
Proof: The Peterson graph is clearly triangle-free, therefore to(G) = 2. The
degree on every vertex is 3, so A(G) + 1 = 4. Since the Peterson graph is not
an odd cycle or a complete graph, we know by Brooks Theorem that
%(G) < A(G) = 3. Since the Peterson graph contains at least one odd cycle
(in the picture above not the outer edges) we know it cannot be 2-colorable.
Therefore, without actually finding a coloring, we know a 3-coloring exists.
So now putting these numbers into Reeds conjecture gives the following
'3 + 1 + 2'
inequality: 3 <
= [3] which is clearly true. So Reeds conjecture
holds for the Peterson graph.
Next we will check the Groetzsch graph, which we examined earlier. Recall that the
second iteration of the Mycielski construction on K2 produces the Groetzsch graph,
shown below.
-48-
Proposition 5.2: Reeds Conjecture holds for the Groetzsch graph.
Proof: The Groetzsch graph is also triangle-free, therefore 00(G) = 2. The
degree of the outer vertices is 4, the degree of the inner vertices is 3, and the
degree of the center vertex is 5. Therefore A(G) = 5 and A(G) + 1 = 6. We
know that each iteration of the Mycielski construction produces a graph that
has chromatic number one greater than the graph before it (shown in the
original explanation of the Groetzsch graph). So K2 has chromatic number 2,
thus two iterations should produce a graph with chromatic number 4. So
X(G) = 4. Putting these numbers into Reeds conjecture gives the following
'5 + 1 + 2'
inequality: 4 <
= [4] which is clearly true. So Reeds conjecture
holds for the Groetzsch graph.
Using the Mycielski construction we can now expand this to show that Reeds
conjecture holds for any iteration of the Mycielski construction on K2.
Proposition 5.3: Reeds Conjecture holds for any iteration of the Mycielski
construction on K2.
Proof: We prove this by induction on the number of iterations. Start with
K2. K2 is clearly 2-colorable, triangle free (so 00(G) = 2) and both vertices
have degree 1. Checking this in Reeds conjecture, we get
2.rii
2
iterations. Let G be the graph after n iterations, and G' be the graph after n +
1 iterations. We know that %(G') = %(G) +1 by constructions, and since both
graphs are triangle-free, we know co(G') = 00(G) = 2. Since the center vertex
= f2]. Now assume that Reeds conjecture holds for n
-49-
always has the highest degree, and is connected to half of the vertices (not
including itself), we know A(G) = - and likewise A(G') = --.
2 2
For each iteration we add one new vertex for each original vertex, plus a final
center vertex. So n(G') = 2n(G) + l. Substituting this into the previous
equations, we get
A(G')-1
A(G)=2W(G) + 1 X=n(G) => A(G) =
. Now we check Reeds conjecture. /(G1) <
Z(G) + l<
A(G') = 2A(G) + 1
A(G') + 1 + u(G')
~2A(G) +1 +1 + oj(G) = 1" 2A(G) + a>(G) J = 2A(G) +
2 2 2
+ 1
=> %(G) <
2A (G) +
2
which is true by the induction hypothesis if
A(G) > 1. Since we started with K2 which has maximum degree one, and the
degree on each iteration strictly increase, this will always be true. Thus
Reeds Conjecture holds for any iteration of the Mycielski construction on
K2.
This proof shows that if we start with K2, in which Reeds conjecture holds, that any
number of iterations of the Mycielski construction will produce a graph that also fits
Reeds conjecture. This is a much better bound than Brooks Theorem gives us, as
ffl(G) = 2 for all iterations and so by averaging it with the upper bound A(G) +1, it
keeps the bound much more reasonable than just A(G).
-50-
So we have proved the conjecture true for some specific examples. Now we wish to
see if the conjecture is true for various classes of graphs. We start with some perfect
graphs, and see if we can prove the conjecture true.
Proposition 5.4: Reeds Conjecture holds for every complete graph, K.
Proof: Let AT be a complete graph. So we know that %(G) = n(G) = co(G)
since every vertex needs its own color, and the largest clique is the graph
itself. Since each vertex is connected to every other vertex in the graph, we
also know that A(G) = n(G) -1. Substituting these values into Reeds
inequality, we get n(G) <
this inequality holds.
n(G) -1 +1 + n(G) '2 n(G)~
2 2
= n(G). So clearly
Proposition 5.5; Reeds Conjecture holds for every bipartite graph, G.
Proof: Let G be a bipartite graph. So we know that x(G) = 2 and co(G) = 2
since each independent set can be colored in one color, and bipartite graphs
are triangle free. We also know A(G) > 1. Substituting these values into
Reeds inequality, we get 2 <
A(G) + 1 + 2
2
Since A(G) > 1, this inequality
holds.
Proposition 5.6: Reeds conjecture holds for every interval graph, G.
Proof: In Proposition 2.4 we showed that for every interval graph G,
Z(G) = a(G). Thus z(G) =2co^ and since
. .. . . o>(G) + A(G) +1
graphs, this gives us j^(G) <-----------.
-51 -
Proposition 5.7; Reeds Conjecture holds for every chordal graph, G.
Proof: In Proposition 2.6 we showed that for every interval graph G,
/(G) = to(G). So using the same argument as Proposition 5.6, we get that
Reeds conjecture holds.
Proposition 5.8; Reeds Conjecture holds for every odd cycle, G.
Proof: Let G be an odd cycle. First suppose G is a triangle. Then G is a
complete graph, and this case has already been proven. So suppose G is an
odd cycle, and n{G) > 5. We know that /(G) = 3, eo(G) = 2 since G is
triangle free, and A(G) = 2. Substituting these values into Reeds inequality,
we get 3 <
2 + 1 + 2
2
= 3.
This inequality clearly holds.
This case also
shows the need for the ceiling on the value
A(G) + l + m(G)
2
because without
the ceiling inequality above would be 3 < and therefore the conjecture
would be false.
Next we will prove Reeds Conjecture for line graphs. This was proven by A. D.
King, Bruce Reed and A. Vetta in [8] in 2005. We will need some preliminary
definitions, as well as a theorem of Edmond, and a theorem of Goldberg and Seymour
in order to complete this proof.
A multigraph is a graph in which multiple edges are permitted between any pair of
vertices. We will assume though that multigraphs are loopless in this paper. Given a
multigraph H, the line graph of H, denoted L(H), is a graph with vertex set E(H),
and two vertices are adjacent in L(H) if and only if their corresponding edges in H
-52-
share at least one vertex. G is a line graph if there is a multigraph H for which
G = L(H). The chromatic index of H, written /'(H), is the chromatic number of
L(H). A fractional vertex c-coloring of a graph G can be described as a set of
stable sets {S,,^,...,^} with weights such that for every vertex v,
i
Xs ves W' = ^ ^ ^ w, = c. The fractional chromatic number of G, written
i=l
X*(G) is the smallest c for which G has a fractional vertex ocoloring. The
fractional chromatic index, Â£'*(#) is equal to the fractional chromatic number of
L(H).
Theorem 5.9 fEdmond 19651: Given
r(ff) = : w = H, |K(W)| is odd j.. = max{A(//),r(ff)}
Theorem 5.10 fCaprara and Rizzi 19981: For any multigraph H,
X\H)Â£ maxll. IA(H)+.7] [r(tf)D.
Proposition 5.11: Reeds Conjecture holds for every line graph, G.
Proof: Consider a multigraph H for which G = L(H). We prove this in two
cases:
3
Case 1: Suppose A(G) > A(H) -1. Then by Theorem 5.9,
X(G) = X\H) < max{Ll.lA(//) + .7j,rrW)X so X(G) <
A(G) + l + __
2__
Case 2: Suppose A(G) < A(H)-l. We will not include all the details of
Reeds proof here, but outline his method of proof. Consider a
-53-
counterexample G = L(H) such that the theorem holds for every line graph
on fewer vertices. We will find a maximum stable set S c V(G) that has a
vertex in every maximum clique in G, and let G' be the subgraph of G
induced on V(G) S. We can see that A(G') < A(G) -1 (since S is maximal)
and a>(G') = co(G) -1. The theorem holds for G' since any induced subgraph
of a line graph is a line graph. So we know j(G') <
A(G) +1 + o)(G)
2
We can construct a proper %(G') + \ -coloring of V(G) by taking a proper
Z(G') -coloring of G' and letting S be the final color class, so
X(G)<
A(G) + l + o>(G)
2
a contradiction.
Now using some earlier bounds from Chapters 2 and 3, we can also prove the
conjecture for graphs with large clique numbers relative to the degree of the graph.
Proposition 5.12: Reeds Conjecture holds for every graph G, where
o(G) = A(G) +1.
Proof. A(G) ++
know x(G) < A(G) +1 by Proposition 3.1, so %(G) < .
Proposition 5.13: Reeds Conjecture holds for every graph G, where a)(G) = A(G).
Proof:
1 . 1 T a tn\ 1 i a in\ 1 Tta rn\ _l 11 V 1 "
= A(G) +1
A(G) + 1 + g>(G) 'A(G) + 1 + A(G) 2A(G) + r _ i > Â§ + 11 h- i
2 2 2 2
-54-
Again, we use x(G) < A(G) + 1 by result 2.1, so
Z(.G)<
A(G) + 1 + 6>(G)
2
Proposition 5.14; Reeds Conjecture holds for every graph G, where
co(G) = A(G) -1.
A(G) +1 + o>(G) A(G) +1 + A(G) -1
J' 2 2
^2^ = ^cnow
X(G) < A(G) for graphs other than complete graphs and odd cycles by
Brooks Theorem. Propositions 5.1 and 5.3 already proved Reeds conjecture
for these two cases, so the result holds for all graphs where co(G) = A(G) -1.
Proposition 5.15: Reeds Conjecture holds for every graph G, where
g)(G) = A(G) 2.
Proof:
A(G) + 1 + Â£(G) A(G) +1 + A(G) 2" "2A(G)-f
2 2 2
= A(G).
So by the same argument as provided in Proposition 5.14, we get that Reeds
conjecture holds.
Finally, Reed shows in his paper where he originally states his conjecture that if
A(G) is sufficiently large and co(G) is sufficiently close to A(G), then the
conjecture holds. Reed provides proofs for this result, as well as algorithms for
finding the colorings required in [10]. Although he doesnt actually provide a value
for sufficiently large, he does prove the result for A(G) > A0 for some A0. He
makes no attempt to compute or minimize this value, but perhaps in future research
he will do so.
-55-
It would appear from the examples and graphs studied so far, that Reeds Conjecture
is true. Perhaps by looking at Reeds method to prove it true for large graphs using
the probabilistic method, a proof could be found that works for all graphs. We look
forward to a proof (or counter-example should the conjecture prove false) by Reed or
someone else in the future.
-56-
REFERENCES
[1] Aldous, Joan M. and Wilson, Robin J. Graphs and Applications; An
Introductory Approach. London: Springer, 2000.
[2] Berge, C. and Chvatal, V. Topics on Perfect Graphs. New York: Elsevier
Science Publishers, 1984.
[3] Borodin, O.V. and Kostachka, A.V. On an Upper Bound of a Graphs
Chromatic Number, Depending on the Graphs Degree and Density. Journal of
Combinatorical Theory, Vol. 23 B (1977) pp. 247-250.
[4] Buckley, Fred and Lewinter, Marty. A Friendly Introduction to Graph Theory.
Upper Saddle River, NJ: Pearson Education, Inc., 2003.
[5] Capobianco, Michael and Molluzzo, John C. Examples and Counterexamples in
Graph Theory. New Yotk: Elsevier North-Holland, 1978.
[6] Diestel, Reinhard. Graduate Texts in Mathematics: Graph Theory. New York:
Springer-Verlag, 1997.
[7] Hajiabolhassan, Hossein and Zhu, Xuding. Circular chromatic number and
Mycielski construction. National Sun Yat-sen University, 2001.
[8] King, A. D., Reed, B.A. and Vetta, A. An Upper Bound for the Chromatic
Number of Line Graphs. Discrete Mathematics and Theoretical Computer
Science; Nancy, France (2005).
[9] Reed, Bruce. A Strengthening of BrooksTheorem. Journal of Combinatorial
Theory, Vol. 76 B (1999) pp. 136-149.
[10] Reed, Bruce. ,A and John Wiley & Sons, Inc. (1995).
[11] Seinsche, D. On a Property of the Class of n-Colorable Graphs. Journal of
Combinatorial Theory, Vol. 16 B (1974) pp. 191-193.
-57-
[12] West, Douglas. Introduction to Graph Theory. Upper Saddle River, NJ:
Prentice-Hall, 1996.
[13] Wikepedia Encyclopedia Four color Theorem, http://www.wikipedia.org.
-58-
*
* |