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: Distinguishing Chromatic Numbers of Bipartite Graphs. | Distinguishing Chromatic Numbers of Bipartite Graphs C. Laflamme and K. Seyffarth Submitted Sep 9 2008 Accepted Jun 18 2009 Published Jun 25 2009 Mathematics Subject Classification 05C15 05C25 Abstract Extending the work of . Collins and A. N. Trenk we characterize connected bipartite graphs with large distinguishing chromatic number. In particular if G is a connected bipartite graph with maximum degree A 3 then XD G 2A 2 whenever G Ka-i a Ka a- 1 Introduction A colouring of a graph G is an assignment of labels colours to the vertices of G the colouring is proper if and only if adjacent vertices receive different labels and the colouring is distinguishing provided that no automorphism of G other than the identity preserves the labels. The distinguishing chromatic number of G written XD G is the minimum number of labels required to produce a colouring that is both proper and distinguishing. The distinguishing chromatic number is introduced by . Collins and . Trenk 3 as a natural extension of the distinguishing number of a graph defined by . Albertson and . Collins 1 . In 3 Collins and Trenk compute the distinguishing chromatic number for various classes of graphs. In particular they characterize the connected graphs with maximum possible distinguishing chromatic number showing that XD G V G if and only if G is a complete multipartite graph 3 Theorem . Further they show that for a connected graph G with maximum degree A XD G 2A with equality if and only if G Ka a or G C6 a cycle of length six 3 Theorem . For connected graphs with A 2 they also completely determine the distinguishing chromatic number. Note that if G is Department of Mathematics and Statistics University of Calgary Calgary Alberta Canada T2N 1N4 laflamme@. Supported by NSERC of Canada Department of Mathematics and Statistics University of Calgary Calgary Alberta Canada T2N 1N4 kseyffar@ THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R76 1 connected and
