2017/09/28 by Alikhani, Saeid, Soltani, Samaneh · 1 citation
#05C15 #05C25 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1709.10021
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) of G is defined similarly, where, in addition, f is assumed to be a proper labeling. Motivated by a conjecture in \citecolins, we prove that if G is a bipartite graph of girth at least six with the maximum degree Δ(G), then χD(G)≤ Δ(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.