Kenneth Rosen Edition 7 Exercise 10.8 Question 23 (Page No. 734)

Question

Find the edge chromatic numbers of
a) Cn, where n ≥ 3. (Cycle with n vertices)

b) Wn, where n ≥ 3  (Wheel with n vertices)

c)Complete graph with n vertices.

Comments

#Doubt

For Cn - I am getting :

2 - When n is even

3- When n is odd.

But for Wn-

I tried to derive. I am getting :

n-1 when n is even

n+1 when n is odd.

but in rosen . It's given n for both the cases of Wn

Answer 1

We obtained the wheel $W_{n}$ when we add an additional vertex to the cycle $C_{n}$, for n>= 3. This means that wheel graph $W_{n}$ have all the vertices present in cycle graph $C_{n}$ and one additional vertex present at the center. This center vertex is connected to other all vertices. So wheel graph $W_{n}$ will have n + 1 vertices.



Here in the image, In $W_{4}$ we can see that all its edges are colored with 4 colors such that no two adjacent edges have the same color. It can't be colored with less than 4 colors because the center vertex is connected to 4 vertices and the edges which connected the center vertex to all the other vertices are adjacent. So we required at least 4 colors.

For $C_{n}$ it is easy to see that.

when n is even, we require 2 colors.
When n is odd, we require 3 colors.

For $K_{n}$ (complete graph),

As a vertex is connected to all other n-1 vertices. We at least require n - 1 colors but when we try to color all its edges with n-1 colors, we see that it can't be done with n-1 colors, We require at least n color to color the edges of the complelete graph.

Answer 2

A) if n is even ϰ=2, else ϰ=3...

B) ϰ=n, n is vertex in a graph(excluding center vertex )

C) ϰ=n, where n is nos of vertex in a graph

Comments

How ? I am asking for edge chromatic no.

---

ohh  sorry, i thought vertex chromatic....i am not pretty sure about complete graph, but other 2 (A and B) are correct...

---

Can you please explain in detail.? In Rosen, it is given n for Wn.

N for complete graph. It"s:

n-1 when n is even?

and n when n is odd?

Answer 3

The edge chromatic number, sometimes also called the chromatic index, of a graph  is fewest number of colors necessary to color each edge of such that no two edges incident on the same vertex have the same color. In other words, it is the number of distinct colors in a minimum edge coloring.

consider triangle edge=3 

now try to color edges minimum no need of color is:2

consider square edge=4

now try to color edges minimum no need of color is :3

consider double triangle edge=5

now try to color edges minimum no need of color is :4

i think this will make some sense