Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: List-Distinguishing Colorings of Graphs. | List-Distinguishing Colorings of Graphs Michael Ferrara1 Breeann Flesch2 Ellen Gethner3 Submitted Nov 10 2010 Accepted Jul 29 2011 Published Aug 5 2011 Mathematics Subject Classification 05C15 05C25 Abstract 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 Albertson 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 y vev 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 E L v for all v. The list-distinguishing number of G Df 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. Keywords Distinguishing Coloring List Coloring List-Distinguishing Coloring 1 Introduction A vertex coloring of a graph G f V G 1 . r is said to be r-distinguishing if no nontrivial automorphism of the graph preserves all of the vertex colors. The distinguishing 1Department of Mathematical and Statistical Sciences University of Colorado Denver Denver CO 80217. . 2Mathematics Department Western Oregon University Monmouth OR 97361. breeannmarie@. Research partially supported by UCD GK12 project NSF award 0742434 3Department of Computer Science and Engineering University of Colorado Denver Denver CO 80217. . THE ELECTRONIC JOURNAL OF COMBINATORICS 18