Chromatic number of a complete bipartite graph

Builds on Complete bipartite graph Chromatic number

Statement

Let $m, n \ge 1$ be integers. Then the chromatic number of the complete bipartite graph $K_{m,n}$ is $2$ .

Remarks

Give one colour to each of the two parts. Each edge joins the two parts, so this is a colouring with $2$ colours. One colour is not enough, because $K_{m,n}$ has an edge. More generally, a bipartite graph with at least one edge has chromatic number $2$ .

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Complete bipartite graph example
Graph colouring definition
K-colourable graph definition
Chromatic number definition
Chromatic number of a complete bipartite graph statement

Tag	`0FJBBCXYPS`
URI	`m2://0FJBBCXYPS`
Kind	statement, proposition
Writing	W0 stub
MSC	05C15
Status	This copy of the site has no build data. Run `m2 status 0FJBBCXYPS`.
Uses	Complete bipartite graph, Chromatic number

Chromatic number of a complete bipartite graph

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here