List-distinguishing colorings of graphs (Q640414)

Summary: A coloring of the vertices of a graph \(G\) is said to be distinguishing provided that no nontrivial automorphism of \(G\) preserves all of the vertex colors. The distinguishing number of \(G\), denoted \(D(G)\), is the minimum number of colors in a distinguishing coloring of \(G\). The distinguishing number, first introduced by Al- bertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature. In this paper, the notion of distinguishing colorings is extended to that of listdistinguishing colorings. Given a family \(L = \{L(v)\}_{v\in V(G)}\) of lists assigning available colors to the vertices of \(G\), we say that \(G\) is \(L\)-distinguishable if there is a distinguishing coloring \(f\) of \(G\) such that \(f (v) \in L(v)\) for all \(v\). The list-distinguishing number of \(G,\, D_\ell (G)\), is the minimum integer \(k\) such that \(G\) is \(L\)-distinguishable for any assignment \(L\) of lists with \(|L(v)| = k\) for all \(v\). Here, we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph.