MAT175 GROUP 2
INDEPENDENT SETS AND CHROMATIC NUMBER
INDEPENDENT SETS
Definition 1. A subset S of V is called an independent set of G if no two vertices of S are
adjacent in G.
Examples:
V: {v1, v2, v3, v4, v5, v6}
S1: {v3, v6} S4: {v4, v5}
G: S2: {v3, v4} S5: {v2, v6}
S3: {v2, v5} S6: {v1}
V: {v1, v2, v3, v4, v5, v6, v7}
S1: {v6, v4}
H: S2: {v2, v5}
S3: {v2, v3, v4}
S4: {v2, v3, v4, v5}
S5: {v1}
S6: {v2, v3, v4, v5, v6, v7}
Definition 2. A vertex independent set S⊆V is called a maximum independent set of G if G has
no independent set S' with |S'|>|S|.
Examples:
From definition 1.
1. The sets S1: {v3, v6}, S2: {v3, v4}, S3: {v2, v5}, S4: {v4, v5}, S5: {v2, v6} are the
maximum independent set of a graph G.
2. The set S6: {v2, v3, v4, v5, v6, v7} is the maximum independent set of a graph G.
J:
Definition 3. A subset K of V is called a covering of G if every edge of G is incident with at least
one vertex K.
Examples:
V: {v1, v2, v3, v4, v5, v6}
K1: {v1, v3, v5, v6}
G: K2: {v2, v4, v1, v6}
K3: {v6, v3, v1, v5}
J:
Theorem 4. A set S⊆V is an independent set of G if and only if V\S is a covering of G.
Proof:
Let S⊆V be an independent set of G. By definition, S is an independent set of G if and
only if no edge of G has both ends in S or, equivalently, if and only if each edge has at
least one end in V\S. But this is so if and only if V\S is a covering of G.
Definition 5. The number of vertices in a maximum independent set is called the independence
number of G and is denoted by α (G ).
Definition 6. The number of vertices in a minimum covering of G is called covering number of
G and is denoted by β (G ).
Definition 7. A covering K is said to be a minimum covering if there is no covering K 0 of G such
that |K 0|<|K|.
Corollary 8. α + β=v .
Proof:
Let S be a maximum independent set of G.
Let K be a minimum covering of G.
Then by Theorem 4, V\K is an independent set and V\S is a covering.
Hence,
|V ¿|≤ α
|V |−|K|≤ α
v−β ≤ α
v≤ α+ β
and
|V ¿|≥ β
|V |−|S|≥ β
v−α ≥ β
v≥ α+ β.
Thus, combining eq. (1) and eq. (2), we have
α +β≤ v ≤ α+β
v=α + β .
Therefore, α + β=v .
CHROMATIC NUMBER
Definition 9. The chromatic number, x (G ), of G is the minimum k for which G is k-colourable; if
x (G )= k, G is said to be k-chromatic.
Examples:
1. Empty Graph: x (G )=1
2. Bipartite Graph: An empty bipartite graph has x (G )=1. A non-empty bipartite graph
has x (G )=2.
x ( K 2 ,4 ) =2
3. Star Graph: A star graph of order n+1, denoted by Sn +1, is the complete bipartite graph
K 1 ,n , where n≥0. So, it has the same chromatic number as a bipartite graph.
x ( S 6 )=2
4. Cycle Graph: A cycle graph of odd order has x ( C2 n+ 1) =3, and that of even order has
x ( C2 n )=2. So, a cycle of even order is also bipartite.
Cycle graph of even order Cycle graph of odd order
x ( C6 ) =2 x ( C5 ) =2
5. Wheel Graph: a wheel graph of odd order has x ( W 2 n+1 ) =4 , and that of even order has
x ( W 2 n )=3 .
Wheel graph of even order Wheel graph of odd order
x ( W 6 )=4 x ( W 7 )=3
6. Complete Graph: Since each vertex is connected to every other vertex, we have
x ( K n )=n .
x ( K 6 )=6
Theorem 10. If Δ (G ) is the maximum of the degrees of the vertices of a graph G. Then
x (G ) ≤ Δ ( G ) +1.
Proof: (by Mathematical Induction)
Let G be a graph with one vertex, V=1.
Then x (G )=1 and Δ (G )=0. This implies, x (G )=1=Δ ( G )+ 1.
Hence, the result is true.
Now, assume that for any graph G with n vertices, x (G ) ≤ Δ ( G ) +1.
Suppose G is a graph with n+1 vertices.
Let v be a vertex such that, deg(v)= Δ (G ) and v 1 , v 2 ,…, v Δ (G ) be the vertices adjacent to v.
Consider the subgraph H=G−v .
Note that, Δ ( H ) ≤ Δ ( G ) . Now, H can be coloured with x ( H ) colours.
Since H has n vertices, by induction hypothesis, x (G−v ) ≤ Δ ( G−v ) +1 .
Hence, x (G−v ) ≤ Δ ( G ) +1. So ( G−v ) can be coloured with at most
Δ (G )+1 colours.
Since, deg(v)= Δ (G ), at least one colour say c, which is not used in v 1 , v 2 ,…, v Δ (G −v ).
Thus, we get Δ (G )+1 colouring of G.
