Chromatic Number_6_29

Question

Let G be a simple undirected graph on n=3x vertices (x>=1) with chromatic number 3, then maximum number of edges in G is

(A) n(n-1)/2

(B) n^(n-2)

(C) nx

(D) n

Comments

Let's try to think it through ,

can it be n(n-1)/2 ? Not always , let's take an example , n=6 . n(n-1)/2 number of edges would signify the graph as a complete graph and for this graph , chromatic number is 6 , so this cannot be the answer.

Let's take other one , n^(n-2) , it's even more than n(n-1)/2 , and no simple graph would exist with such huge number of edges.

As far as option n is concerned , we can always show that with n=6 , we actually get number of edges more than just n.

So according to me , answer must me nx. That is options C.

Answer 1

By using chromatic partitioning ,we can divide the graph into 3 independent sets with x vertices each (like tripartionining similar to bipartition graph).For maximum number of edges a vertex in a set is connected to all the vertices in the other 2 sets but not with vertex in its own set(i.e independent).

If we consider the sets coloured as Red,Blue,Green, each with x vertices each.

Step1.

1.Connect each vertex of Red to every vertex of Blue and green,total possible edges = Number of vertices in Red * (number of vertices in blue +number of vertices in green) = 2x^2

2.Connect each vertex of blue to every vertex of green,total possible edges = number of vertices in blue*number of vertices in green = x^2

Total edges = 2x^2+x^2 =3x^2 =n*x