Graph coloring

Many terms usedthis articledefined inGlossarygraph theory.

A coloring ofGraphan assignmentcolors tovertices such that no two adjacent verticesassignedsame color. Here, "adjacent" means sharingsame edge. Graph coloring colorsequivalent toproblempartioningvertex set into independent sets. The problemcoloringgraph has foundnumberapplications such as scheduling, register allocation inmicroprocessor, frequency assignmentmobile radios,pattern matching.

In general, techniquesgraph coloring concentrate on findingleast numbercolors neededcolorgraph ie. its chromatic number . For examplechromatic number ofcomplete graph vertices(a graphan edge between every two vertices),.

The problemfindingminimum coloring ofgraphNP-hard. The corresponding decision problem(Is therecoloring which uses at most colors?)NP-complete. Therehowever some efficient approximation algorithms that employ Semidefinite programming.

Some properties of

1. iff Gtotally disconnected.

2. iff G hascycleodd length

3. greater thancardinality oflargest complete subgraphG.

4. ,where ismaximum degreeany vertexG.

5. ,any planar Graph G. This famous result, calledfour-color theorem, was stated by P. J. Heawood1890, but remained unproven until 1976, whenwas established by Kenneth AppelWolfgang Haken atUniversityIllinois.

Note: iff means: ifonly if.

Chromatic Polynomials

The chromatic polynomial ofgraph was introduced by BirkhoffLewistheir attack onfour-color theorem.

Let us denote by numberdifferent colorings oflabeled graph G from colors. Two coloringG will be considered different if at least one oflabeled pointsassigneddifferent color.Then,can be shown that will bepolynomial. For example forcomplete graph3 vertices(), sincefirst vertex can be colored ways,second waysso on.

Some propertieschromatic polynomials:

1. , if

2. Let G begraph vertices, edges, components . Then:

a. has degree

b. The coefficient1.

c. The coefficient.

d. The constant term0.

e.

f. The smallest exponent withnon-zero coefficient.

3. The coefficientsevery chromatic polynomial alternatesigns

4. A Graph G vertices istree ifonly .

It remains an unsolved problemcharecterize graphs which havesame chromatic polynomial anddetermine precisely what polynomialschromatic.

See also:

• four-color theorem

• Uniquely Colorable Graphs

• Critical Graphs

• Graph Homomorphisms