Coloring the Two Parts
A complete bipartite graph has two designated parts: vertices in different parts are adjacent, and vertices in the same part are not. This structure makes its vertex coloring unusually direct. When both parts contain vertices, one color for each part gives a proper coloring, and the presence of an edge shows that one color cannot suffice. The cases with an empty part need separate attention: they have no edges, but they need not have no vertices.
A vertex coloring with \(q\) colors is an assignment of colors from a set of \(q\) labels to the vertices. It is proper if the endpoints of every edge receive different colors. A color is allowed to be unused. The chromatic number \(\chi(G)\) is the least number of colors in a proper coloring; by convention, the graph with no vertices has chromatic number \(0\). Thus, a graph with vertices but no edges has chromatic number \(1\), not \(0\).
The Chromatic Number in Every Case
Proof. If \(m=n=0\), the vertex set is empty. The empty assignment is a proper coloring using zero colors, so \(\chi(K_{0,0})=0\). If exactly one of \(m,n\) is zero, the graph has at least one vertex but no edges: every edge would need one endpoint in each part. Assigning one color to every vertex is proper, so its chromatic number is at most \(1\). No coloring with zero colors can assign a color to its nonempty vertex set, so its chromatic number is \(1\). Finally, suppose \(m,n\geq1\). Choose \(x\in X\) and \(y\in Y\). By definition, \(xy\) is an edge, so a proper coloring must give \(x\) and \(y\) different colors; hence at least two colors are required. Assign one color to all of \(X\) and a second color to all of \(Y\). Every edge has one endpoint in each part, so its endpoints receive different colors. This is a proper two-coloring, proving that \(\chi(K_{m,n})=2\). \(\square\)
The argument separates a lower bound from a construction. In the nonempty case, a single edge certifies that one color is insufficient, while coloring by parts supplies a two-coloring. In the edgeless cases, there is no edge-based obstruction at all; instead, the number of vertices distinguishes chromatic number \(0\) from chromatic number \(1\).
Worked Example: Coloring \(K_{2,3}\)
Let \(X=\{a_1,a_2\}\) and \(Y=\{b_1,b_2,b_3\}\). Define \(G=K_{2,3}\) by the vertex set \(V(G)=\{a_1,a_2,b_1,b_2,b_3\}\) and the edge set \(E(G)=\{a_1b_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3\}\). We find and verify an optimal coloring.
Assign red to \(a_1,a_2\), and blue to \(b_1,b_2,b_3\). The six edges are \(a_1b_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3\). Each listed edge has one red endpoint and one blue endpoint, so the coloring is proper. For an independent edge count, each of the two vertices in \(X\) is adjacent to all three vertices in \(Y\), giving \(2\cdot3=6\) edges, which agrees with the list.
Check: The edge \(a_1b_1\) prevents a one-color proper coloring, while the assignment just checked uses two colors. Thus \(\chi(G)=2\). The displayed coloring is optimal, not merely proper.
Proof. Fix vertices \(x_0\in X\) and \(y_0\in Y\). The edge \(x_0y_0\) requires their colors to differ, so the coloring uses exactly two colors; call them red and blue, with \(x_0\) red and \(y_0\) blue. Every \(y\in Y\) is adjacent to \(x_0\), so every vertex of \(Y\) must be blue. Every \(x\in X\) is adjacent to \(y_0\), so every vertex of \(X\) must be red. These assignments are proper because all edges run between the parts. Therefore the two parts are each monochromatic and have opposite colors. \(\square\)
Consequently, for fixed color labels, there are exactly two optimal colorings when both parts are nonempty: either \(X\) is red and \(Y\) blue, or \(X\) is blue and \(Y\) red. If we regard colorings as the same when their color labels are simply renamed, these are one coloring pattern. This rigidity depends on completeness: every vertex in one part must be adjacent to every vertex in the other.
Worked Example: Coloring \(K_{3,1}\)
Let \(X=\{p,q,r\}\) and \(Y=\{s\}\). Define \(G=K_{3,1}\) by \(V(G)=\{p,q,r,s\}\) and \(E(G)=\{ps,qs,rs\}\). Give an optimal coloring and verify its structure.
Color \(p,q,r\) red and \(s\) blue. Checking edge by edge, \(ps\) has red endpoint \(p\) and blue endpoint \(s\); \(qs\) has red endpoint \(q\) and blue endpoint \(s\); and \(rs\) has red endpoint \(r\) and blue endpoint \(s\). All three edges are properly colored. The independent count is \(3\cdot1=3\) edges, matching the edge list.
Check: The edge \(ps\) means one color cannot suffice. Since the coloring above uses two colors, \(\chi(G)=2\). Also, the proposition applies: the three vertices in \(X\) share one color, and the only vertex in \(Y\) has the other.
When a Part Is Empty
If one part is empty, the graph is edgeless, so there are no adjacency constraints on color assignments. If vertices remain, one color is enough and necessary. In an optimal coloring, that one color is assigned to every vertex. This is a different situation from the case where both parts are nonempty: there, an edge forces at least two colors.
Worked Example: A Nonempty Edgeless Graph \(K_{0,4}\)
Let \(X=\varnothing\) and \(Y=\{u,v,w,z\}\). Define \(G=K_{0,4}\) by \(V(G)=\{u,v,w,z\}\) and \(E(G)=\varnothing\). Color all four vertices green.
To check propriety, inspect the edge set: it has no edges, so there is no pair of adjacent vertices that could receive the same color. This coloring uses one color. Since \(V(G)\) has four vertices, a coloring with zero colors cannot assign a color to each vertex. Therefore \(\chi(G)=1\).
Check: The complete-bipartite edge count is \(0\cdot4=0\), in agreement with \(E(G)=\varnothing\). The graph has vertices, so its chromatic number is \(1\), not \(0\).
Worked Example: The Empty Graph \(K_{0,0}\)
Take \(X=Y=\varnothing\). Define \(G=K_{0,0}\) by \(V(G)=\varnothing\) and \(E(G)=\varnothing\). Its unique assignment of colors to vertices is the empty assignment: there are no vertices on which a choice must be made.
The empty assignment is proper because there are no edges whose endpoints could violate the coloring rule. It uses zero colors. Since the definition permits zero colors for the graph with no vertices, \(\chi(G)=0\).
Check: The edge count is \(0\cdot0=0\), consistent with the empty edge set, and the vertex count is \(0\). This distinguishes \(K_{0,0}\) from \(K_{0,4}\): both are edgeless, but only the latter has vertices to color.
Common Mistake: Treating All Edgeless Cases Alike
A frequent error is to say, “A complete bipartite graph always has chromatic number \(2\), because it has two parts.” That argument fails when either part is empty: the existence of two named parts does not guarantee an edge. For example, in \(K_{0,3}\), there is no vertex in one part, so there are no cross-part edges. Assigning two different colors is possible, but it is not optimal; assigning one color to the three vertices is already proper.
The opposite error is to say, “An edgeless graph has chromatic number \(0\).” That confuses having no edges with having no vertices. For \(K_{0,3}\), the vertex set has size \(3\), so a color assignment must give each of those vertices a color. One color suffices and zero colors do not. Only \(K_{0,0}\) has no vertices and therefore has chromatic number \(0\).
For a quick decision, first check whether both part sizes are positive. If they are, a cross-part edge gives the lower bound of two and coloring by parts gives the upper bound of two. If not, count the vertices: no vertices means chromatic number \(0\); at least one vertex and no edges means chromatic number \(1\).
Why the Part Sizes Matter
The complete bipartite case is a useful model for separating two tasks in a coloring argument. To prove that a proposed coloring works, check that every edge has differently colored endpoints. To prove that it is optimal, show that fewer colors cannot work. When both parts are nonempty, one edge supplies the lower bound and the part assignment supplies the construction. When an empty part removes all edges, the obstruction disappears, and the empty vertex set must be distinguished from a nonempty one.
The proposition also provides a stronger verification than checking just one coloring: with two nonempty parts, it describes every proper coloring using at most two colors. Any such coloring must be constant on each part, with opposite colors across the parts. If vertices within a part have different colors in a proposed two-color assignment, some cross-part edge will fail the properness test.
Check Your Understanding
For each question, keep track of both the edge constraints and whether the vertex set is empty.
- What is \(\chi(K_{1,5})\), and what single edge proves that one color is insufficient?
- Let one part have no vertices and the other have seven. Explain why the chromatic number is not zero.
- Prove that \(K_{m,n}\) has \(mn\) edges by counting each edge from its endpoint in one fixed part.
- For \(m,n\geq1\), why must all vertices in \(X\) have the same color in any proper coloring that uses at most two colors?
- State the chromatic number of \(K_{0,0}\), and explain why the empty assignment is a proper coloring.