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 $k$ colors is equivalent to the problem of partioning the vertex set $V$ into $k$ 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 $\chi$. For example the chromatic number of a complete graph of $n$ vertices(a graph with an edge between every two vertices), is $n$.

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 $k$ colors?) is NP-complete. There are however some efficient approximation algorithms that employ Semidefinite programming.

Some properties of χ(G)

1. $\chi (G)=1$ iff G is totally disconnected, meaning no vertex is connected to any other by an edge in G

2. $\chi (G)\geq 3$ iff G has a cycle of odd length

3. $\chi (G)$ is at least the cardinality of the largest complete subgraph of G.

4. $\chi (G)\leq 1+\Delta (G)$ , where $\Delta (G)$ is the maximum degree of G, meaning some vertex in G is adjacent to Δ(G) vertices but none is adjacent to more than Δ(G) vertices.

5. $\chi (G)\leq 4$, 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 $f(G,t)$ the number of different colorings of a labeled graph G from $t$ 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 $f(G,t)$ will be a polynomial in $t$. For example for the complete graph of 3 vertices($K_{3}$), $f(K_{3},t)=t(t-1)(t-2)$ since the first vertex can be colored in $t$ ways, the second in $t-1$ ways and so on.

Some properties of chromatic polynomials:

1. $f(G,t)=0$ , if $t<\chi (G)$

2. Let G be a graph with $p$ vertices, $q$ edges, and $k$ components $G_{1},G_{2},...G_{k}$. Then:

a. $f(G,t)$ has degree $p$

b. The coefficient of $t^{p}$ in $f(G,t)$ is 1.

c. The coefficient of $t^{p-1}$ in $f(G,t)$ is $-q$.

d. The constant term in $f(G,t)$ is 0.

e. $f(G,t)=\Pi _{i=1}^{k}f(G_{i},t)$

f. The smallest exponent of $t$ in $f(G,t)$ with a non-zero coefficient is $k$.

3. The coefficients of every chromatic polynomial alternate in signs

4. A Graph G with $p$ vertices is a tree if and only $f(G,t)=t(t-1)^{p-1}$.

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

• Perfect graph