564 views
1 votes
1 votes

If they asked maximum independent set of complement bipartite graph then answer will be 2 right??  And for bipartite graph it will be max(m,n)

1 Answer

Best answer
0 votes
0 votes

Actually what I think they have meant to ask about the complete bipartite graph (It seems to be spelling mistake in the question)..

For that case , we have the relation between the independence number and chromatic number as :

Independence number >=  Number of vertices / Chromatic number

Secondly chromatic number of a complete bipartite graph is 2.

Hence size of maximal independent set which is independence number >= (m+n) / 2  [ As the graph is Km,n so is the case here ]

                                                                                                        =  ceil[(m + n) / 2]

Hence D) should be the correct option.

 

selected by

Related questions

2 votes
2 votes
0 answers
1
Niharika 1 asked Jan 25, 2018
215 views
how they are drawing DAG.Can someone explain?
0 votes
0 votes
0 answers
2
Niharika 1 asked Oct 29, 2017
198 views
I checked with handshaking lemma I got 3 are not trees. I added all the degree sequence and equalized with 2* no of vertices -1 because if it is tree no of edges = no of ...
0 votes
0 votes
1 answer
3
Niharika 1 asked Oct 29, 2017
448 views
Answer is c right and it is bipartite graph?
1 votes
1 votes
1 answer
4
Niharika 1 asked Oct 28, 2017
332 views
What is order means here and how to solve this?