Distinguishing Chromatic Numbers of Bipartite Graphs

  • C. Laflamme
  • K. Seyffarth

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}$.

Published
2009-06-25
Article Number
R76