The distinguishing chromatic number of bipartite graphs of girth at least six

The distinguishing number D(G) of a graph G is the least integer d such that G has a vertex labeling   with d labels  that is preserved only by a trivial automorphism. The distinguishing chromatic number \chi_{D}(G) of G is defined similarly, where, in addition, f is assumed to be a proper labeling. We prove that if G is a bipartite graph of girth at least six with the maximum degree \Delta (G),  then    \chi_{D}(G)\leq \Delta (G)+۱.  We also obtain an upper bound for \chi_{D}(G) where G is a graph with at most one cycle. Finally, we state a relationship between the distinguishing chromatic number of a graph and its spanning subgraphs.

Keywords:

distinguishing number , distinguishing chromatic number , symmetry breaking