Counting Colorings by One Part
A complete bipartite graph has two parts: every vertex in one part is adjacent to every vertex in the other, and there are no edges within either part. In a proper coloring, each part may use a color more than once, but the colors appearing on opposite parts must be disjoint. This makes it natural to count colorings by first recording how many colors appear on one part.
All graphs in this tutorial are finite and simple. For a graph \(G\), its chromatic polynomial \(P_G(q)\) has the property that, for every nonnegative integer \(q\), \(P_G(q)\) counts the proper colorings of \(G\) using a palette of \(q\) labeled colors. A coloring is proper when the endpoints of every edge receive different colors.
Write \((q)_k=q(q-1)\cdots(q-k+1)\) for the falling factorial, with \((q)_0=1\). Write \(S(s,k)\) for the Stirling number of the second kind: the number of ways to partition a set of \(s\) labeled elements into exactly \(k\) nonempty, unlabeled blocks. Equivalently, if \(k\) particular colors have been selected, \(k!S(s,k)\) counts assignments to the \(s\) labeled vertices that use every one of those colors.
The Formula
Proof. First take \(q\) to be a nonnegative integer, so that a palette of \(q\) labeled colors is defined. Group proper colorings according to the number \(k\) of colors appearing on \(Y\). Since \(s\ge1\), any coloring uses at least one color on \(Y\), and at most \(s\); thus \(1\le k\le s\).
Choose the \(k\) colors that appear on \(Y\), and assign them onto the \(s\) labeled vertices so that every chosen color is used. There are \(\binom{q}{k}\) choices of the color set and \(k!S(s,k)\) onto assignments for that set. Each vertex of \(X\) is adjacent to every vertex of \(Y\), so it must avoid all \(k\) colors used on \(Y\). There are \(q-k\) choices for each of the \(r\) vertices of \(X\), independently, giving \((q-k)^r\) assignments on \(X\). There are no edges within \(X\), so these choices impose no further restrictions. The number of colorings in this case is therefore $$ \binom{q}{k}k!S(s,k)(q-k)^r=S(s,k)(q)_k(q-k)^r. $$ Different values of \(k\) describe disjoint cases, and every proper coloring belongs to exactly one case. Summing gives the stated count for every nonnegative integer \(q\). The right-hand side is a polynomial in \(q\), and it agrees with the chromatic polynomial at infinitely many integer values. Two polynomials that agree at infinitely many values are equal, so the formula holds as a polynomial identity. \(\square\)
The formula is written by counting colors on the part of size \(s\). Counting instead by the colors used on \(X\) gives the same polynomial with \(r\) and \(s\) interchanged. This equality follows directly because either grouping counts the same set of proper colorings, for every nonnegative integer \(q\).
Worked Polynomial Calculations
Worked Example: The Polynomial of \(K_{2,3}\)
Let \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2,y_3\}\), and let the edge set consist of all six pairs \(x_i y_j\). Thus \(K_{2,3}\) has no edges within \(X\) or \(Y\). The relevant values are \(S(3,1)=1\), \(S(3,2)=3\), and \(S(3,3)=1\). The formula gives
Expand each term separately. The first is \(q(q-1)^2=q(q^2-2q+1)=q^3-2q^2+q\). For the second, \((q-1)(q-2)^2=(q-1)(q^2-4q+4)=q^3-5q^2+8q-4\), so \(3q(q-1)(q-2)^2=3q^4-15q^3+24q^2-12q\). For the third, first multiply \(q(q-1)(q-2)=q^3-3q^2+2q\). Hence $$ q(q-1)(q-2)(q-3)^2 =(q^3-3q^2+2q)(q^2-6q+9) =q^5-9q^4+29q^3-39q^2+18q. $$ Adding coefficients gives $$ P_{K_{2,3}}(q)=q^5-6q^4+15q^3-17q^2+7q. $$
Check at \(q=4\): Group directly by the number of colors on \(Y\). If \(Y\) uses one color, there are \(4\) assignments to \(Y\), and each of the two vertices of \(X\) has \(3\) choices, giving \(4\cdot3^2=36\). If \(Y\) uses exactly two colors, choose the pair in \(\binom42=6\) ways and assign both colors onto the three vertices in \(3!=6\) ways. The two vertices of \(X\) each have \(2\) choices, giving \(6\cdot6\cdot2^2=144\). If \(Y\) uses three colors, choose and assign them in \(\binom43\cdot3!=4\cdot6=24\) ways; \(X\) must use the remaining color, giving \(24\cdot1^2=24\). The total is \(36+144+24=204\). Substitution into the polynomial gives \(4^5-6\cdot4^4+15\cdot4^3-17\cdot4^2+7\cdot4=1024-1536+960-272+28=204\), as required.
Worked Example: The Polynomial of \(K_{3,3}\)
For \(K_{3,3}\), take both parts to have three vertices, with all nine cross-part edges and no within-part edges. The same Stirling numbers give $$ P_{K_{3,3}}(q) =q(q-1)^3+3q(q-1)(q-2)^3+q(q-1)(q-2)(q-3)^3. $$
For the first term, \(q(q-1)^3=q^4-3q^3+3q^2-q\). For the second, \((q-1)(q-2)^3=(q-1)(q^3-6q^2+12q-8)=q^4-7q^3+18q^2-20q+8\), so \(3q(q-1)(q-2)^3=3q^5-21q^4+54q^3-60q^2+24q\). For the third, multiply \(q(q-1)(q-2)=q^3-3q^2+2q\) by \((q-3)^3=q^3-9q^2+27q-27\): $$ q(q-1)(q-2)(q-3)^3 =q^6-12q^5+56q^4-126q^3+135q^2-54q. $$ Adding the three expressions yields $$ P_{K_{3,3}}(q)=q^6-9q^5+36q^4-75q^3+78q^2-31q. $$
Check at \(q=4\): If \(Y\) uses one color, there are \(4\cdot3^3=108\) colorings. If it uses two colors, choose them in \(6\) ways, assign both onto \(Y\) in \(3!=6\) ways, and color each of the three vertices of \(X\) in either of the other two colors: \(6\cdot6\cdot2^3=288\). If \(Y\) uses three colors, there are \(4\cdot6=24\) assignments to \(Y\), and each vertex of \(X\) has just one available color, giving \(24\cdot1^3=24\). Thus the total is \(108+288+24=420\). The polynomial gives \(4^6-9\cdot4^5+36\cdot4^4-75\cdot4^3+78\cdot4^2-31\cdot4=4096-9216+9216-4800+1248-124=420\).
Worked Example: A Smaller Check with \(K_{2,2}\)
Let \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2\}\), with all four cross-part edges and no other edges. Since \(S(2,1)=S(2,2)=1\), $$ P_{K_{2,2}}(q)=q(q-1)^2+q(q-1)(q-2)^2 =q(q-1)\bigl((q-1)+(q-2)^2\bigr) =q(q-1)(q^2-3q+3). $$
At \(q=4\), the first case, where \(Y\) uses one color, contributes \(4\cdot3^2=36\). In the second case, \(Y\) uses two colors: choose them in \(\binom42=6\) ways, assign both to the two vertices in \(2\) ways, and color each vertex of \(X\) in either of the two remaining colors, giving \(6\cdot2\cdot2^2=48\). The total is \(36+48=84\). Substituting \(q=4\) into the factored expression gives \(4\cdot3\cdot(16-12+3)=12\cdot7=84\). Also \(K_{2,2}\) is a cycle of length four, and the cycle formula gives \((4-1)^4+(4-1)=81+3=84\), an independent check.
Reading the Formula Correctly
The factor \(S(s,k)(q)_k\) counts assignments on \(Y\) using exactly \(k\) colors: first select and label the colors through the falling factorial, then partition the vertices according to which color they receive. The final factor \((q-k)^r\) counts assignments on \(X\), where every vertex must avoid every color used on \(Y\). In particular, the exponent \(r\) is the size of \(X\), not the size of \(Y\).
A common mistake is to count assignments to \(Y\) using one color as though each of its vertices had several independent choices. For \(K_{2,3}\) with four colors, the incorrect expression \(4\cdot3^3=108\) for this case gives three choices to each vertex of \(Y\) after choosing a color. That does not describe a monochromatic \(Y\): once its single color is selected, all three vertices are forced to receive it. There are \(4\) such assignments to \(Y\), followed by \(3^2=9\) assignments to \(X\), so the correct contribution is \(4\cdot9=36\). The exponent on the choices for \(X\) is \(2\), because \(X\) has two vertices.
The distinction between choosing a color set and assigning colors to vertices matters in every case. For example, in \(K_{2,3}\) with four colors, the two-color case has \(6\) choices of a pair and \(6\) onto assignments to the three labeled vertices of \(Y\), for \(36\) assignments to \(Y\) altogether. It does not have just \(6\) assignments to \(Y\). Then each of the two vertices of \(X\) has \(4-2=2\) available colors, giving \(36\cdot2^2=144\) full colorings in that case.
These examples illustrate why the formula is useful: it replaces a coloring problem with a finite sum of exact counts, while making the restrictions across the two parts explicit. When evaluating at a particular number of colors, inspect each \(k\)-case before multiplying. A color appearing on \(Y\) is unavailable to every vertex of \(X\), but colors may repeat freely within either part.
Check Your Understanding
For each question, make clear which part is being counted first and how many vertices lie in each part.
- Write the formula for \(P_{K_{r,s}}(q)\) when \(s=4\), using \(S(4,k)\) and falling factorials.
- For \(K_{2,3}\) with five available colors, calculate the number of proper colorings in which the three-vertex part uses exactly two colors.
- Explain why the assignments to the two-vertex part contribute a factor \((q-k)^2\) when the three-vertex part uses \(k\) colors.
- Using the formula, derive \(P_{K_{1,3}}(q)\) and simplify it.
- Identify the overcount in using \(\binom{q}{k}k^s\) for assignments to the \(s\)-vertex part when the coloring is required to use exactly \(k\) colors.