Chromatic Number

Definition

The chromatic number of a graph $G$ , written as $\chi(G)$ , is the minimum number of colors needed to color the vertices of $G$ so that no two adjacent vertices have the same color.

A coloring that uses exactly $\chi(G)$ colors is called a minimum proper vertex coloring.

Example

For a triangle graph, each vertex is adjacent to the other two, so all three vertices must have different colors.
Therefore, the chromatic number of a triangle is $3$ .

Main Content

1. Proper Vertex Coloring

A vertex coloring assigns a color to each vertex of a graph.
A coloring is proper if adjacent vertices always get different colors.

A proper vertex coloring is the basic idea behind the chromatic number. The main goal is not just to color the graph, but to do it efficiently using as few colors as possible. The chromatic number is the smallest number of colors that still keeps the coloring proper.

Example

Consider a path graph with four vertices:

A — B — C — D

This graph can be colored as:

A = Red
B = Blue
C = Red
D = Blue

Only 2 colors are needed, so the graph is properly colored with 2 colors.

Important observations

If a graph has no edges, then all vertices can have the same color, so $\chi(G)=1$ .
If a graph has at least one edge, at least 2 colors may be needed.
The coloring depends only on adjacency, not on the shape of the drawing.

2. Chromatic Number of Common Graph Types

Different families of graphs have known chromatic numbers.
These standard results help in solving many graph theory problems quickly.

Important graph classes and their chromatic numbers

a) Complete graphs $K_n$

Every pair of vertices is adjacent.
Each vertex must have a distinct color.
So, $\chi(K_n)=n$ .

Example:

$K_3$ (a triangle) needs 3 colors.
$K_4$ needs 4 colors.

b) Bipartite graphs

Vertices can be divided into two sets so that every edge goes between the sets.
These graphs can always be colored using 2 colors, provided they have at least one edge.
So, for any nonempty bipartite graph, $\chi(G)=2$ .

Example:

Any even cycle like $C_4$ or $C_6$ is bipartite and needs only 2 colors.

c) Cycles

If the cycle has an even number of vertices, it is bipartite and needs 2 colors.
If the cycle has an odd number of vertices, it needs 3 colors.

Examples:

$C_4$ : $\chi(C_4)=2$
$C_5$ : $\chi(C_5)=3$

A simple coloring for $C_5$ :

1 — 2 — 3 — 4 — 5 — back to 1

This fails with only 2 colors because the odd length creates a conflict. A third color solves the problem.

d) Trees

Trees are connected graphs with no cycles.
Every tree with at least one edge is bipartite.
Therefore, $\chi(T)=2$ for any tree with more than one vertex.

3. Properties and Bounds of Chromatic Number

The chromatic number has several useful properties that help estimate or determine it.
It is influenced by the graph’s edges, cycles, and cliques.

Key properties

a) Clique number lower bound

A clique is a set of vertices where every pair is connected.
If the largest clique has size $\omega(G)$ , then: $\chi(G) \ge \omega(G)$
Reason: all vertices in a clique need different colors.

Example:

If a graph contains a triangle, then at least 3 colors are needed.

b) Maximum degree upper bound

If the maximum degree of a graph is $\Delta(G)$ , then: $\chi(G) \le \Delta(G)+1$
This is a basic and very useful bound.
It means no vertex needs more than one extra color beyond its number of neighbors.

c) Brooks’ theorem

For a connected graph that is neither a complete graph nor an odd cycle: $\chi(G) \le \Delta(G)$
This gives a stronger upper bound in many cases.

d) Chromatic number is difficult to compute

For general graphs, finding the exact chromatic number is a hard problem.
It belongs to the class of computationally difficult problems.
For large graphs, approximation and heuristics are often used.

Small illustrative diagram for coloring

A simple triangle:

A / \ B---C

Coloring:

A = Red
B = Blue
C = Green

Three different colors are necessary because every vertex is adjacent to the other two.

Working / Process

1. Identify adjacent vertices

First, list all pairs of vertices connected by an edge.
These pairs cannot receive the same color.

2. Assign colors carefully

Start coloring one vertex.
Move to adjacent vertices and ensure no conflict occurs.
If a conflict appears, introduce a new color.

3. Minimize the number of colors

Continue checking whether a coloring can be done with fewer colors.
The smallest successful number is the chromatic number.

Example process on a path graph

For A — B — C — D:

Color A with Red
Color B with Blue
Color C with Red
Color D with Blue

Only 2 colors are needed, so the chromatic number is 2.

Example process on a triangle

For vertices A, B, C all mutually connected:

Color A with Red
Color B with Blue
C cannot be Red or Blue because it touches both
Color C with Green

So the chromatic number is 3.

Advantages / Applications

Exam scheduling

Each exam can be treated as a vertex.
An edge is drawn between two exams if a student takes both.
The chromatic number gives the minimum number of time slots needed.

Frequency assignment

In wireless communication, nearby transmitters should not use the same frequency.
Graph coloring helps assign frequencies without interference.

Map coloring and resource allocation

Adjacent regions on a map can be assigned different colors.
More generally, the idea applies to allocating resources to conflicting tasks, machines, or processes.

Summary

The chromatic number is the minimum number of colors needed for a proper vertex coloring.
It tells us how to color a graph so adjacent vertices are different.
Common graphs such as complete graphs, bipartite graphs, cycles, and trees have well-known chromatic numbers.
Important terms to remember: chromatic number, proper coloring, vertex coloring, clique, bipartite graph, complete graph, cycle, chromatic number bound