A Note on the Equitable Choosability of Complete Bipartite Graphs

Abstract

In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A $k$-assignment, $L$, for a graph $G$ assigns a list, $L(v)$, of $k$ available colors to each $v\in V(G)$, and an equitable $L$-coloring of $G$ is a proper coloring, $f$, of $G$ such that $f(v)\in L(v)$ for each $v\in V(G)$ and each color class of $f$ has size at most $\lceil |V(G)|/k\rceil$. Graph $G$ is said to be equitably $k$-choosable if an equitable $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies $K_{n,m}$ is equitably $k$-choosable if $k\ge \max \{n,m\}$ provided $K_{n,m}\ne K_{2l+1,2l+1}$. We prove $K_{n,m}$ is equitably $k$-choosable if $m\le \lceil (m+n)/k\rceil (k-n)$ which gives $K_{n,m}$ is equitably $k$-choosable for certain $k$ satisfying $k<\max \{n,m\}$. We also give a complete characterization of the equitable choosability of complete bipartite graphs that have a partite set of size at most 2.

9 pages