Skip to content
Home » Chromatic number Connectivity

Chromatic number Connectivity

Here is a clear, complete, and exam-oriented explanation of Chromatic Number and Connectivity — perfect for Discrete Mathematics, Graph Theory, and BCA/MCA/Engineering exams.

⭐ 1. Chromatic Number (Graph Coloring)

Graph coloring is one of the most important topics in Graph Theory.
The chromatic number of a graph tells us the minimum number of colors needed to color its vertices so that:

No two adjacent vertices have the same color.

⭐ A. Vertex Coloring

A proper coloring assigns colors to vertices such that:

[
\text{If vertices } u \text{ and } v \text{ are adjacent, then } color(u) \neq color(v)
]

⭐ B. Chromatic Number

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

[
\chi(G)
]

is the minimum number of colors needed for a proper coloring.

⭐ C. Simple Examples

✔ Example 1: Path graph (Pₙ)

A path has chromatic number:

[
\chi(P_n) = 2 \quad (n \ge 2)
]

Alternate colors.

✔ Example 2: Cycle graph (Cₙ)

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

Odd cycles require 3 colors.

✔ Example 3: Complete graph (Kₙ)

Every vertex is adjacent to all others.

[
\chi(K_n) = n
]

Maximum possible chromatic number.

✔ Example 4: Bipartite graph

If a graph is bipartite:

[
\chi(G) = 2
]

Used in job assignments, matching, scheduling.

⭐ D. Chromatic Polynomial

A polynomial that counts the number of ways to color a graph with k colors.
Important concept but used less in exams.

⭐ E. Applications of Chromatic Number

✔ Timetable scheduling (no two overlapping classes same teacher/room)
✔ Map coloring (four color theorem)
✔ Register allocation in compilers
✔ Frequency assignment in communication networks
✔ Job scheduling (avoid conflict tasks)
✔ AI constraint satisfaction problems

⭐ 2. Connectivity of Graphs

Connectivity describes how strongly vertices are connected in a graph.

⭐ A. Connected Graph

A graph ( G ) is connected if:

There is a path between every pair of vertices.

If not → disconnected graph.

Disconnected graph contains components (maximal connected subgraphs).

⭐ B. Vertex Connectivity (κ(G))

The vertex connectivity of a graph is:

[
\kappa(G) = \text{minimum number of vertices whose removal disconnects the graph}
]

Meaning:

  • Remove κ(G) vertices → graph becomes disconnected.
  • Removing fewer than κ(G) vertices → graph remains connected.

Examples:

✔ Complete graph ( K_n ):

[
\kappa(K_n) = n-1
]
Most strongly connected.

✔ Cycle graph ( C_n ):

[
\kappa(C_n) = 2
]

✔ Tree:

[
\kappa(T) = 1
]
Removing any leaf disconnects.

⭐ C. Edge Connectivity (λ(G))

The edge connectivity of a graph is:

[
\lambda(G) = \text{minimum number of edges whose removal disconnects the graph}
]

Examples:

  • For cycle graph (C_n): λ = 2
  • For complete graph (K_n): λ = n−1
  • For a tree: λ = 1

⭐ D. Relationship Between Connectivities

For every graph:

[
\kappa(G) \le \lambda(G) \le \delta(G)
]

Where:

  • κ(G) = vertex connectivity
  • λ(G) = edge connectivity
  • δ(G) = minimum degree of G

This is an important exam point.

⭐ E. Cut Vertices & Cut Edges

✔ Cut Vertex (Articulation Point)

A vertex whose removal increases the number of connected components.

Used in network reliability.

✔ Cut Edge (Bridge)

An edge whose removal disconnects the graph.

Trees consist only of bridges.

⭐ F. Strong and Weak Connectivity (Directed Graphs)

In a directed graph (digraph):

⭐ Strongly Connected

Every vertex is reachable from every other vertex.

[
u \to v \quad \text{and} \quad v \to u
]

⭐ Weakly Connected

If we ignore directions (convert edges to undirected), the graph becomes connected.

⭐ Applications of Connectivity

✔ Network reliability
✔ Social networks
✔ Internet and router design (resilience)
✔ Road/transport networks
✔ Communication systems
✔ Power grid design
✔ Determining critical nodes/edges
✔ AI path planning
✔ Cluster detection

⭐ Quick Exam-Oriented Summary

Chromatic Number (χ(G)):

Minimum number of colors to color vertices so that adjacent vertices have different colors.

Important chromatic numbers:

  • Path Pₙ → 2
  • Cycle Cₙ → 2 (even), 3 (odd)
  • Complete graph Kₙ → n
  • Bipartite graph → 2

Connectivity:

✔ Connected graph
Every pair of vertices connected by a path.

✔ Vertex connectivity κ(G)
Minimum vertices removing which disconnects the graph.

✔ Edge connectivity λ(G)
Minimum edges removing which disconnects the graph.

✔ Relation:
[
\kappa(G) \le \lambda(G) \le \delta(G)
]

✔ Cut vertex/bridge:
Vertex/edge whose removal disconnects the graph.

✔ Strong vs Weak connectivity (digraphs)