The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
333 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 \left(G\right)\geq a\left(G\right)$
  2. $\chi \left(G\right)\leq  a\left(G\right)$
  3. $a\left(G\right)\geq \frac{n}{\chi \left(G\right)}$
  4. $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$
  5. None of the above.
asked in Graph Theory by Veteran (42.9k points)
edited ago by | 333 views

2 Answers

+11 votes
Best answer

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

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

$α\left(G\right) \chi \left(G\right) \geq n.$ (its a theorem),
option C.
 
answered by Veteran (15.4k points)
edited ago 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.
Counter ex for option (A) χ(G)≥a(G) , is Cycle graph with n vertices(n is even) has χ(G) = 2 and a(G) = n/2.

So option (A)is wrong.
+1 vote

 

(A) χ(G) ≥ a(G) ,counter ex :Cycle graph with n vertices(n is even) has χ(G) = 2 and a(G) = n/2 .Hence (A) is False.

(B)χ(G)≤a(G) ,counter ex :Complete graph with n vertices  has  χ(G) = n and a(G) = 1 .Hence (B) is False.

(C)a(G)≥n/χ(G), is always True.

Theorem: 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 or

a(G)≥n/χ(G) .

The correct answer is (C)a(G)≥n/χ(G) 

answered by Veteran (13.7k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,156 questions
36,980 answers
92,147 comments
34,822 users