List distinguishing parameters of trees
A coloring of the vertices of a graph G G is said to be distinguishing  provided no nontrivial automorphism of G G preserves all of the vertex colors. The distinguishing number  of G G , D(G) D ( G ) , is the minimum number of colors in a distinguishing coloring of G G . The distinguishing chromatic number  of G G , ?D(G) ? D ( G ) , is the minimum number of colors in a distinguishing coloring of G G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L={L(v)}v?V(G) L = { L ( v ) } v ? V ( G ) of lists of available colors to the vertices of G G , we say that G G is (properly) L L -distinguishable  if there is a (proper) distinguishing coloring f f of G G such that f(v)?L(v) f ( v ) ? L ( v ) for all v v . The list distinguishing number  of G G , D?(G) D ? ( G ) , is the minimum integer k k such that G G is L L -distinguishable for any list assignment L L with |L(v)|=k | L ( v ) | = k for all v v . Similarly, the list distinguishing chromatic number  of G G , denoted ?D?(G) ? D ? ( G ) is the minimum integer k k such that G G is properly L L -distinguishable for any list assignment L L with |L(v)|=k | L ( v ) | = k for all v v . In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T T , D?(T)=D(T) D ? ( T ) = D ( T ) , ?D(T)=?D?(T) ? D ( T ) = ? D ? ( T ) , and ?D(T)?D(T)+1 ? D ( T ) ? D ( T ) + 1 .
distinguishing coloring distinguishing chromatic number list distinguishing coloring list distinguishing chromatic number proper distinguishing coloring