On the roots of chromatic polynomials

被引:15
作者
Brown, JI [1 ]
机构
[1] Dalhousie Univ, Dept Math Stat & Comp Sci, Halifax, NS B3H 3J5, Canada
关键词
D O I
10.1006/jctb.1997.1813
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
It is proved that the chromatic polynomial of a connected graph with n vertices and in edges has a root with modulus at least (m-1)/(n-2); this bound is best possible for tries and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a nonreal root and that there is a graph with n vertices whose chromatic polynomial has a root with imaginary part greater than root n/4. (C) 1998 Academic Press.
引用
收藏
页码:251 / 256
页数:6
相关论文
共 22 条