Graph Coloring

Introduction

Graph coloring: assignment of labels (colors) to graph elements, typically vertices or edges, under constraints. Purpose: prevent adjacent elements sharing the same color. Origin: problems in scheduling, map coloring, register allocation. Importance: foundational in graph theory and combinatorics, with numerous applications in computer science, operations research, and mathematics.

"Graph coloring is a simple concept with profound consequences in mathematics and computer science." -- Douglas B. West

Basic Concepts

Graph Definitions

Graph G = (V, E), where V = vertices, E = edges. Simple graph: no loops or multiple edges. Adjacent vertices: connected by edge. Degree deg(v): number of edges incident to vertex v.

Coloring Definition

Coloring: assignment of colors from a set C to graph elements. Proper coloring: no two adjacent elements share same color. Typical types: vertex coloring, edge coloring.

Types of Coloring

Vertex coloring: assign colors to vertices. Edge coloring: assign colors to edges. Face coloring (planar graphs): colors assigned to faces.

Terminology

Color class: set of vertices/edges with the same color. Chromatic number: minimum number of colors needed for proper vertex coloring. Chromatic index: minimum number of colors needed for proper edge coloring.

Vertex Coloring

Definition

Vertex coloring: map f: V → C such that f(u) ≠ f(v) if (u,v) ∈ E. Goal: minimize |C|.

Chromatic Number

χ(G): smallest number of colors for proper vertex coloring. Range: 1 ≤ χ(G) ≤ |V|. Special cases: bipartite graphs χ(G)=2, complete graphs χ(G)=|V|.

Properties

χ(G) ≥ ω(G) (clique number). If G is bipartite, χ(G)=2 or 1 if edgeless. Upper bound often by Δ(G)+1 (maximum degree + 1).

Greedy Coloring

Assign colors sequentially to vertices choosing smallest available color. Complexity: O(|V|+|E|). May not produce optimal coloring.

Edge Coloring

Definition

Edge coloring: assignment of colors to edges so that adjacent edges differ in color. Adjacent edges share a vertex.

Chromatic Index

χ'(G): minimal number of colors for proper edge coloring. Vizing's Theorem: χ'(G) = Δ(G) or Δ(G)+1.

Classes of Graphs

Class 1 graphs: χ'(G)=Δ(G). Class 2 graphs: χ'(G)=Δ(G)+1. Determining class is non-trivial.

Applications

Scheduling, frequency assignment, register allocation in compilers.

Chromatic Number

Definition and Bounds

χ(G): minimum colors for vertex coloring. Bounds: ω(G) ≤ χ(G) ≤ Δ(G)+1.

Perfect Graphs

Graphs where χ(H)=ω(H) for every induced subgraph H. Includes bipartite, chordal graphs.

Brooks' Theorem

For connected simple graphs not complete or odd cycle, χ(G) ≤ Δ(G).

Examples

Complete graph K_n: χ(K_n)=n. Odd cycle C_2k+1: χ=3.

Planar Graphs and Coloring

Planar Graphs

Graphs embeddable in plane without edge crossings. Euler's formula: |V|-|E|+|F|=2, F=faces.

Four Color Theorem

Every planar graph's vertices can be colored with ≤ 4 colors. Proven by Appel and Haken (1976).

Five Color Theorem

Proof simpler; every planar graph is 5-colorable.

Applications

Map coloring, network visualization, circuit design.

Algorithms

Greedy Algorithm

Sequential vertex coloring with smallest available color. Simple, fast, but not optimal.

Backtracking

Search-based approach to find optimal colorings. Exponential time worst-case.

DSATUR Algorithm

Degree of Saturation heuristic: color vertices by number of differently colored neighbors. Effective for many graphs.

Approximation and Heuristics

Algorithms trading optimality for speed. E.g., largest degree first, recursive largest first.

Computational Complexity

Decision Problems

k-coloring problem: decide if χ(G) ≤ k. NP-complete for k ≥ 3.

NP-Completeness

First proven by Karp (1972). No known polynomial-time algorithm for general graphs.

Special Cases

Polynomial time: bipartite graphs (2-coloring), trees, cycles (except odd cycles for 2-coloring).

Parameterized Complexity

Fixed-parameter tractability explored for treewidth, maximum degree.

Applications

Scheduling

Task assignment avoiding conflicts. Colors represent time slots or resources.

Frequency Assignment

Assigning frequencies in wireless networks to avoid interference.

Register Allocation

Compilers use graph coloring to allocate CPU registers efficiently.

Map Coloring

Coloring political maps so adjacent regions differ in color.

Pattern Matching and Puzzle Solving

Used in pattern recognition, Sudoku variants, and other combinatorial puzzles.

Variants and Extensions

List Coloring

Each vertex has a list of allowable colors. Problem: find coloring respecting lists.

Precoloring Extension

Some vertices precolored; extend to proper coloring of entire graph.

Fractional Coloring

Colors assigned fractionally; relaxation of chromatic number.

Weighted Coloring

Vertices have weights; goal to minimize weighted sum or number of colors.

Examples

Complete Graph K5

Vertices: 5. Edges: 10. Chromatic number χ(K5)=5.

Bipartite Graph K3,3

Vertices partitioned into 3 and 3. Chromatic number χ=2.

Cycle Graph C7

7 vertices in a cycle. Chromatic number χ=3 (odd cycle).

Planar Graph Example

Graph with 6 vertices and 9 edges, 4-colorable by Four Color Theorem.

Tables

Chromatic Numbers of Common Graphs

Vizing's Theorem Edge Coloring Classes

Formulas and Algorithms

Chromatic Number Bound

ω(G) ≤ χ(G) ≤ Δ(G) + 1

Greedy Coloring Algorithm (Pseudocode)

Input: Graph G = (V,E)Initialize color[v] = None for all v in VFor each vertex v in V (in given order): Let used_colors = {color[u] | u adjacent to v and color[u] ≠ None} Assign to color[v] the smallest positive integer not in used_colorsOutput: color assignment color[v] for all v

Vizing's Theorem Statement

For any simple graph G, χ'(G) ∈ {Δ(G), Δ(G) + 1}

References

• West, D.B. "Introduction to Graph Theory," 2nd Ed., Prentice Hall, 2001, pp. 100-150.
• Diestel, R. "Graph Theory," 5th Ed., Springer, 2017, pp. 200-250.
• Appel, K. and Haken, W. "Every Planar Map is Four Colorable," Illinois Journal of Mathematics, vol. 21, 1977, pp. 429-567.
• Karp, R.M. "Reducibility Among Combinatorial Problems," Complexity of Computer Computations, 1972, pp. 85-103.
• Vizing, V.G. "On an Estimate of the Chromatic Class of a p-Graph," Diskret. Analiz., vol. 3, 1964, pp. 25-30.