in Graph Theory
660 views
0 votes
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
660 views

3 Comments

should be 3
0
0
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?
0
0
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.
0
0

Please log in or register to answer this question.

Related questions