Graph Colouring

Introduction

Graph coloring assigns colors to graph elements (vertices/edges) such that adjacent elements have different colors. Used in scheduling, register allocation, frequency assignment, and more.

Vertex Coloring

Definition

A vertex coloring assigns colors to vertices such that:

  • Adjacent vertices have different colors
  • No edge connects two vertices of the same color

Proper Coloring

A coloring is proper if no two adjacent vertices share the same color.

Example 1: Triangle

  1(Red)
 / \
2   3
  • Vertex 1: Red
  • Vertex 2: Blue (can’t be Red - adjacent to 1)
  • Vertex 3: Green (can’t be Red or Blue)

Need 3 colors minimum for triangle.

Example 2: Square

1(R) --- 2(B)
|         |
4(B) --- 3(R)
  • Vertex 1: Red
  • Vertex 2: Blue
  • Vertex 3: Red (not adjacent to 1)
  • Vertex 4: Blue (not adjacent to 2)

Need 2 colors for square!

Example 3: K₅

Complete graph with 5 vertices

Every vertex connected to every other.

Need 5 colors - one per vertex.

Chromatic Number

Definition

The chromatic number χ(G) is the minimum number of colors needed to properly color G.

Examples

χ(K_n) = n

  • Complete graph needs n colors

χ(C_n) = 2 if n is even, 3 if n is odd

  • Even cycles: 2 colors alternate
  • Odd cycles: need 3 colors

χ(Trees) = 2

  • All trees are bipartite

χ(Empty graph) = 1

  • No edges, one color for all

Bounds on Chromatic Number

Lower Bound 1: Clique Number

χ(G) ≥ ω(G)

Where ω(G) = size of largest clique

Why? All vertices in clique need different colors.

Lower Bound 2: Independence Number

χ(G) ≥ v / α(G)

Where α(G) = size of maximum independent set

Why? Independent set can share one color.

Upper Bound: Maximum Degree

χ(G) ≤ Δ(G) + 1

Where Δ(G) = maximum degree

Why? Greedy algorithm needs at most Δ+1 colors.

Brooks’ Theorem

For connected graph (not complete or odd cycle):

χ(G) ≤ Δ(G)

Better bound! Usually need Δ colors (not Δ+1).

Four Color Theorem

Every planar graph: χ(G) ≤ 4

Amazing result! Any map needs at most 4 colors.

Five Color Theorem

Easier to prove: Every planar graph needs ≤ 5 colors.

Greedy Coloring Algorithm

Algorithm

1. Order vertices: v₁, v₂, ..., vₙ
2. For each vertex vᵢ:
   - Assign smallest color not used by neighbors

Example

Graph:

1 -- 2 -- 3
|    |
4 -- 5

Order: 1, 2, 3, 4, 5

Coloring:

  • v₁: Color 1 (first vertex)
  • v₂: Color 2 (adjacent to v₁)
  • v₃: Color 1 (not adjacent to v₁)
  • v₄: Color 2 (adjacent to v₁)
  • v₅: Color 3 (adjacent to v₂ and v₄)

Result: 3 colors used

Complexity

Time: O(V + E)

Space: O(V)

Optimality

Not guaranteed optimal! Order matters.

Different order may give fewer colors.

Welsh-Powell Algorithm

Improvement: Order vertices by decreasing degree.

Why? High-degree vertices constrain more - color first.

Bipartite Graphs

Chromatic Number

χ(Bipartite) = 2

Why? Two sets - each set same color.

Example

Set A: 1, 2, 3 (Red)
Set B: 4, 5 (Blue)

Edges only between A and B

Need exactly 2 colors.

Testing Bipartiteness

Algorithm: BFS/DFS with 2 colors

1. Start with any vertex, color it 1
2. Color all neighbors color 2
3. Color their neighbors color 1
4. If conflict arises → not bipartite
5. If successful → bipartite

Edge Coloring

Definition

An edge coloring assigns colors to edges such that:

  • Adjacent edges have different colors
  • Adjacent = share a common vertex

Chromatic Index

χ’(G) = minimum colors needed for edge coloring

Vizing’s Theorem

For any graph G:

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

Two classes:

  • Class 1: χ’(G) = Δ(G)
  • Class 2: χ’(G) = Δ(G) + 1

Example 1: K₃

  1
 / \
2---3

Edges: (1,2), (2,3), (1,3)

Coloring:

  • (1,2): Red
  • (2,3): Blue
  • (1,3): Green

χ’(K₃) = 3 = Δ(K₃)

Class 1 graph.

Example 2: K₄

Complete graph with 4 vertices
Δ = 3

χ’(K₄) = 3

Even complete graph needs Δ colors (if even vertices).

Example 3: K₅

Complete graph with 5 vertices
Δ = 4

χ’(K₅) = 5 = Δ + 1

Odd complete graph needs Δ+1 colors.

Applications

1. Scheduling

Problem: Schedule exams so no student has conflicts

Solution:

  • Vertices = exams
  • Edge if students take both exams
  • Color = time slot

χ(G) = minimum time slots needed.

2. Register Allocation

Problem: Assign CPU registers to variables

Solution:

  • Vertices = variables
  • Edge if variables live simultaneously
  • Color = register

χ(G) = minimum registers needed.

3. Map Coloring

Problem: Color countries so neighbors differ

Solution:

  • Vertices = countries
  • Edge if countries share border
  • Four Color Theorem: need ≤ 4 colors

4. Frequency Assignment

Problem: Assign frequencies to radio stations

Solution:

  • Vertices = stations
  • Edge if stations interfere
  • Color = frequency

χ(G) = minimum frequencies needed.

5. Sudoku

Problem: Fill 9×9 grid with digits 1-9

Solution:

  • Graph coloring with 81 vertices
  • Edges represent constraints
  • 9 colors for digits 1-9

6. Timetabling

Problem: Create class schedule

Solution:

  • Vertices = classes
  • Edge if classes conflict (same teacher/room)
  • Colors = time slots

Special Graphs

Complete Graphs

χ(Kₙ) = n

Need n colors - every pair adjacent.

Cycles

χ(Cₙ) = 2 if n even, 3 if n odd

Even cycles: Alternate 2 colors

Odd cycles: Need 3rd color

Trees

χ(Tree) = 2

Trees are bipartite.

Wheels

χ(Wₙ) = 3 if n even, 4 if n odd

Wheel = cycle + center vertex

Planar Graphs

χ(Planar) ≤ 4

Four Color Theorem.

Graph Coloring Complexity

Computational Complexity

Decision problem: Can G be colored with k colors?

NP-complete for k ≥ 3

Polynomial for k = 2 (bipartiteness test)

Approximation

No good approximation unless P = NP

Hard to approximate within factor n^(1-ε)

Practical Algorithms

Heuristics:

  • Greedy algorithms
  • Backtracking
  • Simulated annealing
  • Genetic algorithms

Chromatic Polynomial

Definition

P(G, k) = number of ways to properly color G with k colors

Example: Path P₃

1 -- 2 -- 3

P(P₃, k) = k(k-1)(k-1) = k(k-1)²

Why?

  • v₁: k choices
  • v₂: k-1 choices (not v₁’s color)
  • v₃: k-1 choices (not v₂’s color)

Example: Triangle K₃

  1
 / \
2---3

P(K₃, k) = k(k-1)(k-2)

Why?

  • v₁: k choices
  • v₂: k-1 choices
  • v₃: k-2 choices (not v₁ or v₂)

Properties

P(G, k) is a polynomial in k

P(G, 0) = 0 (can’t color with 0 colors)

Degree = v (number of vertices)

Chromatic number: smallest k where P(G, k) > 0

List Coloring

Definition

Each vertex v has a list L(v) of available colors.

Goal: Color from lists so adjacent vertices differ.

List Chromatic Number

χₗ(G) = minimum k such that G is colorable from any assignment of k-element lists.

Relation

χₗ(G) ≥ χ(G)

List coloring is harder!

Example

Graph: K₃

Lists:

  • v₁: {Red, Blue}
  • v₂: {Red, Green}
  • v₃: {Blue, Green}

Solution:

  • v₁: Red
  • v₂: Green
  • v₃: Blue

All from their lists, no conflicts!

Fractional Chromatic Number

Definition

Relaxation of graph coloring using fractional assignments.

χf(G) ≤ χ(G)

Properties

χf(Kₙ) = n

χf(K₂,₂) = 2

Useful in optimization and linear programming.

Key Points for Exams

  1. Vertex coloring: adjacent vertices different colors
  2. Chromatic number χ(G): minimum colors needed
  3. χ(Kₙ) = n, χ(Cₙ) = 2 or 3, χ(Tree) = 2
  4. Greedy algorithm: color vertices in order
  5. χ(G) ≤ Δ(G) + 1 (maximum degree bound)
  6. Brooks’ Theorem: χ(G) ≤ Δ(G) for most graphs
  7. Four Color Theorem: χ(Planar) ≤ 4
  8. Edge coloring: χ’(G) is Δ or Δ+1 (Vizing)
  9. Applications: scheduling, register allocation, map coloring
  10. NP-complete: finding χ(G) is hard for k ≥ 3

Practice Problems

  1. Find χ(K₄). How many colors needed?

  2. Color a square graph. What’s χ(C₄)?

  3. True or False: All trees need exactly 2 colors.

  4. Find chromatic number of this graph:

    1 -- 2
|    |
3 -- 4 -- 5

  5. Use greedy algorithm to color path P₅.

  6. What’s χ(W₆) for wheel graph?

  7. How many colors needed for K₃,₃?

  8. Edge color K₃. What’s χ’(K₃)?

  9. If Δ(G) = 5, what’s maximum χ(G)?

  10. Prove that χ(G) ≥ 2 if G has an edge.