Welcome to Junming Xu's Website                           

 
 Homepage     My books      Research  Graduate Programs  Students  Courses  Others   Related links
 
 
     

Homepage

 
 
 
 
Preface
Contents 
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
 
 
 
 
 

 

 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.