tailieunhanh - Báo cáo toán học: "The Distinguishing Chromatic Number"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The Distinguishing Chromatic Number. | The Distinguishing Chromatic Number Karen L. Collins Dept. of Math. and Comp. Sci. Wesleyan University Middletown CT 06459-0128 kcollins@ Ann N. Trenk Dept. of Math. Wellesley College Wellesley MA 02481 atrenk@ Submitted Jun 10 2005 Accepted Nov 6 2005 Published Feb 15 2006 Mathematics Subject Classification 05C15 05C25 Abstract In this paper we define and study the distinguishing chromatic number XD G of a graph G building on the work of Albertson and Collins who studied the distinguishing number. We find XD G for various families of graphs and characterize those graphs with XD G u G and those trees with the maximum chromatic distingushing number for trees. We prove analogs of Brooks Theorem for both the distinguishing number and the distinguishing chromatic number and for both trees and connected graphs. We conclude with some conjectures. 1 Introduction In 1 Albertson and Collins study the distinguishing number of a graph inspired by the following problem given a ring of seemingly identical keys that open different doors how many colors are needed to distinguish them In the language of graph theory this is the question of how many colors are needed to color the vertices of the cycle Cn so that the only automorphism of the graph which preserves colors is the identity. In this problem there is no requirement that the coloring be proper. Interestingly the cycles C3 C4 and C5 require 3 colors but cycles with 6 or more vertices need only 2 colors see Theorem . Albertson and Collins study the problem for graphs in general using the following definitions. Definition A labeling of the vertices of a graph G h V G 1 . r is said to be r-distinguishing or just distinguishing provided no automorphism of the graph preserves all of the vertex labels. The distinguishing number of a graph G denoted by D G is the minimum r such that G has an r-distinguishing labeling. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R16 1 In this paper we study the