Skip to content
Home » Graph coloring

Graph coloring

Below is a complete, simple, and exam-oriented explanation of Graph Coloring — perfect for BCA/MCA/Engineering/Discrete Mathematics.

⭐ GRAPH COLORING – DETAILED DISCUSSION

Graph Coloring is a way of assigning colors to the vertices (or edges or regions) of a graph following certain rules.
It is one of the most important concepts in graph theory with wide real-world applications.

⭐ 1. What Is Graph Coloring?

Graph coloring is the process of assigning colors to elements of a graph such that certain constraints are satisfied.

The most common type is vertex coloring:

✔ Vertex Coloring

Assign colors to vertices so that:

[
\text{If } (u, v) \in E,\ \text{then } color(u) \ne color(v)
]

Adjacent vertices must have different colors.

⭐ 2. Chromatic Number (χ(G))

The chromatic number of a graph ( G ), written as:

[
\chi(G)
]

is the minimum number of colors needed to properly color all vertices of the graph.

⭐ 3. Proper Coloring – Rules

A proper coloring means:

✔ No two adjacent vertices have the same color
✔ Only the minimum required colors are used
✔ The goal is to minimize the number of colors

⭐ 4. Examples of Chromatic Numbers

✔ Complete Graph Kₙ

Every vertex connects to all others.

[
\chi(K_n) = n
]

✔ Path Graph Pₙ

[
\chi(P_n) = 2
]

Alternate coloring.

✔ Cycle Graph Cₙ

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

✔ Bipartite Graph

[
\chi(G) = 2
]

✔ Star Graph

[
\chi = 2
]

⭐ 5. Types of Graph Coloring

Graph coloring is not limited to vertices. There are other types:

⭐ A. Vertex Coloring (most important)

Used for scheduling, timetabling, registers, and resource allocation.

⭐ B. Edge Coloring

Color edges so that:

[
\text{Adjacent edges have different colors}
]

Chromatic index (χ′(G)) = minimum number of colors needed.

Used in:

  • Traffic light scheduling
  • Channel assignment

⭐ C. Face Coloring (Map Coloring)

Used for coloring regions (planar graph faces).

Four Color Theorem:

Any planar map can be colored with 4 or fewer colors.

⭐ D. Total Coloring

Color both vertices and edges so that:

  • No two adjacent vertices have same color
  • No two adjacent edges have same color
  • An edge and its endpoint do not share the same color

⭐ 6. Methods of Graph Coloring

✔ 1. Greedy Coloring Algorithm

Assign colors one by one to each vertex:

  • Pick a vertex
  • Use the smallest available color
  • Move to next vertex

Not optimal but fast.

Example:
Order: A, B, C, D
Colors: 1, 2, 1, 3

✔ 2. Backtracking Algorithm

Try all color combinations; backtrack when conflict occurs.

Guarantees optimal coloring but slow (exponential time).

✔ 3. DSATUR Algorithm

Color vertex with highest degree of saturation (distinct colored neighbors).

Used in practical applications.

✔ 4. Welsh-Powell Algorithm

Sort vertices by decreasing degree, then use greedy coloring.

⭐ 7. Applications of Graph Coloring

Graph coloring is widely used in real life:

✔ 1. Timetable Scheduling

Teachers, rooms, and timeslots are vertices; conflicts are edges.

✔ 2. Map Coloring

Neighboring regions must have different colors.

✔ 3. Register Allocation in Compilers

Assign CPU registers to variables without conflict.

✔ 4. Frequency Assignment in Wireless Networks

Adjacent towers cannot use the same frequency.

✔ 5. Task Scheduling

Tasks that cannot run at the same time get different colors.

✔ 6. Sudoku

It is a graph coloring problem.

✔ 7. Circuit Design

Avoid interference by assigning different tracks/colors.

⭐ 8. Chromatic Polynomial (Optional for exams)

A polynomial counting number of ways to color a graph using k colors.

Example for tree with n vertices:

[
P(k) = k(k-1)^{n-1}
]

Because root has k choices, each child has (k−1) choices.

⭐ 9. Important Theorems

✔ Brook’s Theorem

For connected graph G (except complete or odd cycle):

[
\chi(G) \le \Delta(G)
]

Where Δ(G) = maximum degree.

✔ Four Color Theorem

Every planar graph can be colored with at most 4 colors.

⭐ 10. Quick Exam-Oriented Summary

✔ Graph Coloring

Assign colors to vertices so no two adjacent vertices have same color.

✔ Chromatic Number χ(G)

Minimum colors required.

✔ Important Results

  • Path Pₙ → 2
  • Cycle even → 2
  • Cycle odd → 3
  • Complete graph Kₙ → n
  • Bipartite graph → 2

✔ Types

  • Vertex
  • Edge
  • Face
  • Total coloring

✔ Applications

Scheduling, maps, compilers, networks, task allocation.