Alikhani, S., Soltani, S. (2016). The distinguishing chromatic number of bipartite graphs of girth at least six. Algebraic Structures and Their Applications, 3(2), 81-87.

Saeid Alikhani; Samaneh Soltani. "The distinguishing chromatic number of bipartite graphs of girth at least six". Algebraic Structures and Their Applications, 3, 2, 2016, 81-87.

Alikhani, S., Soltani, S. (2016). 'The distinguishing chromatic number of bipartite graphs of girth at least six', Algebraic Structures and Their Applications, 3(2), pp. 81-87.

Alikhani, S., Soltani, S. The distinguishing chromatic number of bipartite graphs of girth at least six. Algebraic Structures and Their Applications, 2016; 3(2): 81-87.

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

^{}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.

[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.