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: Chromatic Roots of a Ring of Four Cliques. | Chromatic Roots of a Ring of Four Cliques . Dong Mathematics and Mathematics Education National Institute of Education Nanyang Technological University Singapore f Gordon Royle School of Mathematics Statistics University of Western Australia Australia gordon@ Dave Wagner Department of Combinatorics and Optimization University of Waterloo Canada dgwagner@ Submitted Mar 10 2011 Accepted Jul 8 2011 Published Jul 22 2011 Mathematics Subject Classification 05C15 05C31 11C08 65H04 Abstract For any positive integers a b c d let Ra b c d be the graph obtained from the complete graphs Ka Kb Kc and Kd by adding edges joining every vertex in Ka and Kc to every vertex in Kb and Kd. This paper shows that for arbitrary positive integers a b c and d every root of the chromatic polynomial of Ratb c d is either a real number or a non-real number with its real part equal to a b c d 1 2. Keywords graph chromatic polynomial chromatic root ring of cliques 1 Introduction A ring of cliques is a graph whose vertex set is the disjoint union of cliques arranged in a cyclic order such that the vertices of each clique are joined to all the vertices in the two neighbouring cliques. If the cliques have size a1 a2 . an then we denote this graph by Rai a2 . an. Figure 1 shows the graph 2 2 3 3- Corresponding author. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P151 1 7 2 3 3 Figure 1 The graph R2 2 3 3 Graphs with this structure have occurred several times previously in the study of chromatic polynomials and their roots. In particular in proving that there are non-chordal graphs with integer chromatic roots Read 6 considered the graphs in this family with a1 1 and he also used slightly different notation . Rings of cliques cropped up again recently in a preliminary investigation of the algebraic properties of chromatic roots Cameron 1 and in the course of this investigation the chromatic roots of many of these graphs were computed. .
