The Gateway to Computer Science Excellence
0 votes
If $G$ is a bipartite graph with 6 vertices and 9 edges, then the chromatic number of $\overline G$ =
in Graph Theory by Boss | 135 views
should be 3
Yes ans is 3.

Try constructing bipartite graph first, by dividing vertices into 2 groups. Here it is very easy 3 vertices on one side and 3 on other side. And all possible edges (9 edges) are connected.

Take complement of it. Find chromatic number.

Anybody got any shortcut?
max   no of edge in Bipartite graph=(n^2)/4 , when n is equally distributed both side.

here n=6, max edge =9 both side n/2  vertices means 3.

so G' will be disconnected having two component with 3 vertices each make odd cycle with 3-3 edges.

so chromatic no 3.

Please log in or register to answer this question.

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
52,218 questions
59,895 answers
118,134 users