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

Alikhani, Saeid; Soltani, Samaneh

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

Document Type : Research Paper

Authors

Department Mathematics, Yazd University 89195-741, Yazd, Iran

Abstract

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)+1$. 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

References

[1] M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996), #R18.
[2] K.L. Collins and A.N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (1) (2006),
#R16.
[3] D.W. Cranston, Proper distinguishing colorings with few colors for graphs with girth at least 5. arXiv
preprint arXiv:1707.05439
[4] J. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, Boca Raton, 2004.
[5] C. Laflamme and K. Seyffarth, Distinguishing chromatic numbers of bipartite graphs, Electron. J. Combin.
16 (1) (2009), #R76.