##### Maths - 1M - The chromatic no. of the complete bipartite gra...

The chromatic no. of the complete bipartite graph K_{m,n} (m,n > 1) is...

|m-n| | |

min (m, n) | |

2 | |

max(m, n) |

The chromatic no. of the complete bipartite graph K_{m,n} (m,n > 1) is...

|m-n| | |

min (m, n) | |

2 | |

max(m, n) |

In K

_{m,n}, we have each of m vertices of 1 set , say m connected to each of n vertices of other set , say n and similarly for n set also . But no edge between vertices within set m or n.In other words , m and n are disjoint sets.So members of m can be coloured by 1 colour and the members of other set by other 1 colour.So 2 colours.Also , we have a theorem which states that :

A graph is bipartite iff it is bichromatic.Hence 2 should be correct.