GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
232 views

Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours needed for a valid colouring of $G$. A set $B\subseteq V$ is an independent set if no pair of vertices in $B$ is connected by an edge. Let $a(G)$ be the number of vertices in a largest possible independent set in $G$. In the absence of any further information about $G$ we can conclude.

  1. $\chi (G)\geq a(G)$
  2. $\chi (G)\leq   a(G)$
  3. $a(G)\geq n/\chi (G)$
  4. $a(G)\leq  n/\chi (G)$
  5. None of the above.
asked in Graph Theory by Veteran (38.7k points)  
edited by | 232 views

1 Answer

+8 votes
Best answer

Independence number : Size of largest maximum independent set. a(G) (it covers all adjacent vertices)
Chromatic Number : Minimum No. of color required to properly color the graph .χ(G)

 
The vertices of G can be partitioned into χ(G) monochromatic classes. Each class is an independent set, and hence cannot have size larger than α(G)

α(G) χ(G)  n (its a theorem)
option C

 
answered by Veteran (15.1k points)  
selected by
what i think is it should be option d . take the example of a wheel graph. with w4 . it will contain 5 vertices. and its chromatic number will 3.  so 5/3= 1.something . and the independent set . will be one.  the option  does not hold for it i think .

plus take  a complete graph. and apply . independent set = zero. vertex = n . and chromatic number is n.

so c is saying 0>=1. not true.
a(G) be the number of vertices in a largest possible independent set in G.
Independent set w4 will be 2.
ohh got it. i missed that it is vertex. solved using cut set.


Top Users Sep 2017
  1. Habibkhan

    6362 Points

  2. Warrior

    2234 Points

  3. Arjun

    2212 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1716 Points

  8. makhdoom ghaya

    1660 Points

  9. A_i_$_h

    1552 Points

  10. rishu_darkshadow

    1512 Points


25,991 questions
33,561 answers
79,414 comments
31,029 users