Graph coloring

A 3-coloring of a graph

Many terms used in this article are defined in the Glossary of graph theory.

A coloring of a Graph is an assignment of colors to the vertices such that no two adjacent vertices are assigned the same color. Here, "adjacent" means sharing the same edge. Graph coloring with colors is equivalent to the problem of partioning the vertex set into independent sets. The problem of coloring a graph has found a number of applications such as scheduling, register allocation in a microprocessor, frequency assignment in mobile radios, and pattern matching.

In general, techniques for graph coloring concentrate on finding the least number of colors needed to color the graph ie. its chromatic number . For example the chromatic number of a complete graph of vertices(a graph with an edge between every two vertices), is .

The problem of finding a minimum coloring of a graph is NP-hard. The corresponding decision problem(Is there a coloring which uses at most colors?) is NP-complete. There are however some efficient approximation algorithms that employ Semidefinite programming.

Some properties of

1. iff G is totally disconnected.

2. iff G has a cycle of odd length

3. is greater than the cardinality of the largest complete subgraph of G.

4. ,where is the maximum degree of any vertex in G.

5. , for any planar Graph G. This famous result, called the four-color theorem, was stated by P. J. Heawood in 1890, but remained unproven until 1976, when it was established by Kenneth Appel and Wolfgang Haken at the University of Illinois.

Note: iff means: if and only if.

Chromatic Polynomials

The chromatic polynomial of a graph was introduced by Birkhoff and Lewis in their attack on the four-color theorem.

Let us denote by the number of different colorings of a labeled graph G from colors. Two coloring of G will be considered different if at least one of the labeled points is assigned a different color.Then, it can be shown that will be a polynomial in . For example for the complete graph of 3 vertices(), since the first vertex can be colored in ways, the second in ways and so on.

Some properties of chromatic polynomials:

1. , if

2. Let G be a graph with vertices, edges, and components . Then:

a. has degree

b. The coefficient of in is 1.

c. The coefficient of in is .

d. The constant term in is 0.

e.

f. The smallest exponent of in with a non-zero coefficient is .

3. The coefficients of every chromatic polynomial alternate in signs

4. A Graph G with vertices is a tree if and only .

It remains an unsolved problem to charecterize graphs which have the same chromatic polynomial and to determine precisely what polynomials are chromatic.

See also:

• four-color theorem

• Uniquely Colorable Graphs

• Critical Graphs

• Graph Homomorphisms

Referenced By