Theory and Application of Graphs
==========================================================================
Chapter 6
Coloring
Theory
In the history of graph theory, the problems involving the coloring of graphs have received
considerable attention -- mainly because of one problem, the four-color problem proposed in 1852: whether four
colors will be enough to color the countries of any map so that no two countries
which have a common boundary are assigned the same color.
Since more than 150 years, in the process of attempt at the four-color problem, one has greatly
developed and enriched coloring theory of graphs. In this chapter, we will introduce
basic concepts of vertex-coloring and edge-coloring of a graph and two graphic parameters, chromatic number and
edge-chromatic number, closely related to the two types of colorings. We will present two classical results on coloring theory of graphs,
Brooks' theorem and Vizing's theorem. We will also present the equivalence of certain problems concerning vertex-coloring and edge-coloring with the four-color problem by Tait's theorem.
We will find the so-called chromatic number (rep. edge-chromatic number) of a graph is the least number of independent subsets
(resp. matchings) into which the vertex-set (resp. edge-set) of the graph can be partitioned. In view of this, the coloring theory
provided in this chapter is a continuation and extensions of theory concerning independent sets and
matchings.
Apart from its own theoretical interest, the study of coloring of graphs is also motivated by its increasing importance in
applications of the real-world problems. Unfortunately, as far no efficient algorithm is
known for solving these problems.
|
