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

χ_{D} (G)

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

Δ (G)

, then

χ_{D} (G) \leq Δ (G) + 1

. We also obtain an upper bound for

χ_{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.