Vertex Coloring | Sahithyan's Notes

Aka. proper vertex coloring. The assignment of colors to vertices such that no two adjacent vertices have the same color. If a maximum of $m$ colors are used, then referred to as $m$ -coloring.

k-Colorable Graph

A graph is $k$ -colorable iff it can be colored using $k$ colors.

G\text{ is }k\text{-Colorable} \implies G\text{ is }{j}\text{-Colorable}\quad \forall k \lt j \le |V(G)|

If a graph is 2-colorable, then it is bipartite.

Chromatic Number

The minimum number of colors required for a proper vertex coloring. Denoted by $\chi(G)$ .

Equal for all isomorphic graphs. $\chi(K_n) = n$ .

For $n \gt 2$ ,

\chi(C_n) = \begin{cases} 2 & \text{if }n\text{ is even} \\ 3 & \text{if }n\text{ is odd} \end{cases}

For $\chi{K_{m,n}} = 2$ . One color for each bipartite group.

Suppose $G$ and $H$ are undirected simple connected graphs with at least 2 vertices. Then:

If $I$ = $G$ and $H$ joined with a single edge then $\chi(I) = \text{max}(\chi(H), \chi(G))$
If $I = G \triangledown H$ = all verties of $G$ are connected with all vertices of $H$ then $\chi(I) = \chi(H) + \chi(G)$ .

Every graph can be colored with one more color than the maximum vertex degree.

Chromatic Polynomial

A polynomial representing the number of proper vertex colorings of a graph for $x$ number of colors. Denoted as $P(G, x)$ . Depends on graph structure.

For $K_n$ ,

P(G,x) = \prod_{i=0}^{n-1} {x - i}

For a null graph with $n$ vertices,

P(G,x) = x^n

For $K_n$ :

P(G,x) = \frac{x!}{(x-n)!}

For a path of $n$ vertices: $P(G,x) = x(x-1)^{n-1}$ .

For $K_{m,n}$ , $P(G,x)=x(x-1)^{m+n-1}$ .

For a graph with multiple connected components $\set{ G_1, G_2, \dots, G_k }$ ,

P(G, x) = \prod_{i=1}^{k} P(G_i, x)

In the polynomial, absolut value of the coeffecient of $x^{n-1}$ gives the number of edges in the graph where $n$ is the number of vertices.

Deletion–Contraction Method

A recursive method to compute the chromatic polynomial.

P(G, x) = P(G - e, x) - P(G/e, x)

Here:

$e$ : an edge
$(G-e)$ : resulting graph when $e$ is removed from $G$
$(G/e)$ : resulting graph when ednpoints of $e$ is merged

Explanation:

counts colorings excluding conflicts (via subtraction)
reduces complex graphs step-by-step

Key properties: • parallel edges after contraction can be treated as one • loops result in zero colorings

Algorithms

Greedy Coloring Algorithm

Assigns colors sequentially based on a chosen vertex order.

Steps:

Initialize empty coloring
Choose an order of vertices
For each vertex:
- assign smallest available color not used by neighbors
- create new color if needed
repeat until all vertices are colored

Simple. Efficient. Not optimal. Depends on vertex ordering.

Other algorithms

Several algorithms aim to improve solution quality.

Welsh–Powell algorithm
DSatur algorithm

Applications

Map Coloring

Assign colors to regions such that adjacent regions differ.

Regions are modelled as vertices and shared boundaries are modelled as edges.

Timetable Scheduling

Assign time slots to exams such that no student has overlapping exams.

Exams are modelled as vertices. Shared students are edges. Time slots are colors. Minimum number of required time slots is the chromatic number.

Other Applications

Register allocation in compilers
Mobile frequency assignment
Sudoku solving