Distinguishing Chromatic Numbers of Bipartite Graphs

Abstract

Extending the work of K.L. Collins and A.N. Trenk, we characterize connected bipartite graphs with large distinguishing chromatic number. In particular, if $G$ is a connected bipartite graph with maximum degree $\Delta \geq 3$, then $\chi_D(G)\leq 2\Delta -2$ whenever $G\not\cong K_{\Delta-1,\Delta}$, $K_{\Delta,\Delta}$.