TAILIEUCHUNG - Báo cáo toán học: "List-Distinguishing Colorings of Graphs"

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

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học