Module 7
▪ Chromatic Number
▪ Chromatic Portioning
▪ Chromatic Polynomial
▪ Matching
▪ Covering
▪ Four Color Theorem
▪ A vertex coloring or a coloring is an assignment of colors to the vertices of the
graph.
▪ A coloring is said to be proper coloring if adjacent vertices receives different color
▪ The minimum number of color required for a proper coloring of a graph is called
chromatic no. of the graph denoted by 𝜒(𝐺)
▪ The chromatic no. of the graph is 𝑘 then 𝐺 is said to be 𝑘 −coloring.
▪ Assigning minimum number of color to each vertex such that no two adjacent vertices receive
same color. B C
A
- Vertex/ Node
- Edge/Link
E D
▪ 3 Colors are enough to provide proper vertex coloring for the considered graph
෪𝑛 = 1
▪𝜒 𝐾
▪ 𝜒 𝐾𝑛 = 𝑛
▪ 𝜒 𝐾𝑚,𝑛 = 2
2, 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
▪ 𝜒 𝐶𝑛 = ቊ
3, 𝑛 𝑖𝑠 𝑜𝑑𝑑
▪ 𝜒 𝑃𝑛 = 1
(1) (4)
d(B)=3 d(C)=2
B C
1
0 0
3
(3) A
d(A)= 0
2
2
E D
0
1 2
0
d(E)=2 d(D)=3
(5) (2)
▪ If 𝐺 is a connected simple graph & is neither an odd cycle nor a complete graph
then 𝜒 𝐺 ≤ Δ
▪ Every planar graph is 5-vertex colourable
▪ Denote 𝜋𝑘 (𝐺) be the number of distinct 𝑘 −coloring of 𝐺 then 𝜋𝑘 (𝐺) will be interms
of 𝑘 is called chromatic polynomial of graph 𝐺
▪ Example: Distinct 3-coloring of 𝐾3 then 𝜋3 𝐾3 = 6
Remark:
▪ If 𝐺 is empty graph (Null graph) of order 𝑛 then 𝜋𝑘 𝐺 = 𝐾 𝑛
▪ If 𝐺 is complete graph, of order n & 𝑘 > 𝑛 then 𝜋𝑘 𝐺 = 𝑘 𝑘 − 1 … 𝑘 − 𝑛 − 1
▪ If 𝐺 is simple, then 𝜋𝑘 𝐺 = 𝜋𝑘 𝐺 − 𝑒 − 𝜋𝑘 𝐺. 𝑒
▪ Graph G = (𝐺 − 𝑒) - (𝐺. 𝑒)
▪ Step 1
▪ Last step:
▪ 𝐾4 − 3𝐾3 + 3𝐾2 − 𝐾1 = 𝐾 4 − 3𝐾 3 + 3𝐾 2 − 𝐾 = 𝐾 𝐾 − 1 3
▪ A subset, 𝑀 of 𝐸(𝐺) is called a matching in a graph 𝐺 =< 𝑉, 𝐸 > if no two ends of an
edges in 𝑀 are adjacent in 𝐺
▪ If 𝑀 is a matching in a graph 𝐺, then the two ends of an edge in 𝑀 are said to be
matched under 𝑀
▪ A matching 𝑀 saturates a vertex 𝑣 & 𝑣 is said to be 𝑀 −saturated, if some edge of 𝑀
incident with 𝑣 otherwise 𝑣 is said to be unsaturated
▪ A matching, 𝑀 of a graph 𝐺 is said to be perfect matching or perfect if every vertex
of 𝐺 is 𝑀 𝑠𝑎𝑡𝑢𝑟𝑎𝑡𝑒𝑑
▪ A covering of a graph 𝐺 is a subset 𝑘 of 𝑉(𝐺) such that every edge of 𝐺 has atleast
one end in 𝑘. A covering 𝑘 of a graph 𝐺 is a minimum covering if 𝐺 has no other
covering 𝑘′ with 𝑘 ′ < |𝑘|
