tailieunhanh - Báo cáo toán học: "Graphs with chromatic roots in the interval (1, 2)"

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: Graphs with chromatic roots in the interval (1, 2). | Graphs with chromatic roots in the interval 1 2 Gordon F. Royle School of Computer Science Software Engineering University of Western Australia Nedlands WA 6009 Australia gordon@ Submitted Apr 18 2007 Accepted Aug 22 2007 Published Aug 31 2007 Mathematics Subject Classification 05C15 Abstract We present an infinite family of 3-connected non-bipartite graphs with chromatic roots in the interval 1 2 thus resolving a conjecture of Jackson s in the negative. In addition we briefly consider other graph classes that are conjectured to have no chromatic roots in 1 2 . 1 Introduction The chromatic polynomial of a graph G is the function P G k that counts the number of k-colourings of G when k is a natural number. It is well known that P G k is a polynomial with degree equal to the number of vertices of G and there is an extensive literature on the relationship between the properties of a graph and its chromatic polynomial. For general backgound information and references to much of this literature we refer the reader to the recent book on chromatic polynomials by Dong Koh Teo 2 . One aspect of the study of chromatic polynomials that has received considerable recent interest is the problem of the distribution of the chromatic roots of a graph that is the real and complex zeros of the chromatic polynomial. In a comprehensive survey paper Jackson 4 describes much of this work and presents a number of open problems and conjectures. One of these conjectures arises from attempts to extend the portion of the real line on which the behaviour of the chromatic polynomial is completely understood. In particular we have complete knowledge of the real roots of P G x for all values of x 32 27 as described in the following fundamental theorem. Theorem 1 See Jackson 4 . If G is a loopless graph with n vertices c components and b blocks which are not isolated vertices then a P G x is non-zero with sign 1 n for x 2 1 0 THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N18 1 ifi