3 - Graph Coloring

Problem Description

Graph coloring problem is to assign colors to certain elements of a graph subject to certain constraints.

Vertex coloring is the most common graph coloring problem. The problem is, given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. The other graph coloring problems like Edge Coloring (No vertex is incident to two edges of same color) and Face Coloring (Geographical Map Coloring) can be transformed into vertex coloring.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial	[- Brute-force search (1852)] Lawler; 1976 (1976) Schiermeyer; 1994 (1994) Beigel & Eppstein; 1995 (1995) Beigel & Eppstein; 2005 (2000) Robson (1986) Sch¨oning (1999) Hirsch (1998) Johnson 1988 (1988) Alon and Kahale (1997)
Polynomial > 3
Cubic
Quadratic	Vlasie (1995)
nlogn
Linear	Karger, Blum (1997)
logn