---
title: "Graph coloring and chromatic number"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:define-graph-coloring-chromatic-number"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/define-graph-coloring-chromatic-number
site: BCT Engineering
---

# Graph coloring and chromatic number

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2071 Bhadra, 2+2 marks; 2070 Magh, 2+2 marks; 2070 Bhadra, 4 marks (asked 3 times)
- Video: [Graph Theory | Graph Coloring & Chromatic Number of Graph | Discrete Mathematics by GP Sir](https://www.youtube.com/watch?v=HKRFK8W5JlE) — Dr.Gajendra Purohit
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/define-graph-coloring-chromatic-number
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Define the term graph coloring and the chromatic number of a graph.

## Short answer

Graph coloring assigns colors to vertices so adjacent vertices get different colors. The chromatic number (chi) is the minimum number of colors needed. For example, chi(Kn)=n, chi(bipartite graphs)=2, chi(C5)=3.

## Answer

#### Graph coloring
A **graph coloring** (vertex coloring) of a simple graph is an assignment of colors to its vertices so that no two adjacent vertices get the same color. A coloring that satisfies this rule is called *proper*.

#### Chromatic number
The **chromatic number** χ(G) is the smallest number of colors needed for a proper coloring of G. To show χ(G) = k, show that k colors suffice and that fewer than k colors cannot work.

#### Standard values
| Graph | χ |
|---|---|
| Kₙ | n |
| Cₙ, n even | 2 |
| Cₙ, n odd | 3 |
| Bipartite graph with at least one edge, tree | 2 |
| Any planar graph | ≤ 4 (Four Color Theorem) |

Also χ(G) ≤ Δ(G) + 1 (greedy coloring).

#### Example
Triangle K₃ with vertices a, b, c: all three are mutually adjacent, so they need 3 different colors, χ(K₃) = 3. The square C₄ (a–b–c–d–a): color a, c red and b, d blue, so χ(C₄) = 2.

Application: scheduling exams, where courses are vertices, an edge joins courses sharing a student, and colors are time slots.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In a proper vertex coloring:
   A. No two vertices get the same color
   B. All adjacent vertices get the same color
   C. Edges are given different colors
   D. No two adjacent vertices get the same color
   Answer: D. Adjacent vertices must differ in color; non-adjacent ones may share. (Key point: Proper coloring)

2. The chromatic number chi(G) is:
   A. The smallest number of colors for a proper coloring
   B. The largest degree of G
   C. The number of vertices
   D. The number of colors used by any coloring
   Answer: A. chi(G) is the minimum number of colors that suffices. (Key point: Chromatic number)

3. To show chi(G) = k you must show:
   A. k colors suffice only
   B. k colors suffice and fewer than k cannot work
   C. Every vertex has degree k
   D. Fewer than k colors suffice
   Answer: B. Both an upper bound (a coloring) and a lower bound are needed. (Key point: Proving chi = k)

4. What is chi of the cycle C5?
   A. 2
   B. 4
   C. 3
   D. 5
   Answer: C. Odd cycles cannot be 2-colored since alternating fails on returning to the start; 3 colors work. (Key point: Standard values)

## Related in Discrete Structure

- [Draw K6 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k6-chromatic-number) — Discrete Structure, chapter 4, asked 4×
- [Draw K5 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k5-chromatic-number) — Discrete Structure, chapter 4, asked 4×
- [Draw K3,4 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-chromatic-number) — Discrete Structure, chapter 4
- [Chromatic number of K5, Km,n, Cp](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Achromatic-number-k5-kmn-cp) — Discrete Structure, chapter 4
- [Draw K3,4 and C5; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-c5-chromatic) — Discrete Structure, chapter 4, asked 4×
- [Draw K4,5 and C6; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k45-c6-chromatic) — Discrete Structure, chapter 4, asked 4×

## Related in other subjects

- [nth Fibonacci term prime check](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afibonacci-nth-prime) — Computer Programming, chapter 6
- [Define co-ordination number with example](https://www.bctengineer.com/question.md?key=semester_2%2Fengineering_chemistry%3Adefine-coordination-number) — Engineering Chemistry, chapter 6
- [Define effective atomic number (EAN)](https://www.bctengineer.com/question.md?key=semester_2%2Fengineering_chemistry%3Adefine-ean) — Engineering Chemistry, chapter 6