On the roots of chromatic polynomials

被引：15

作者：

Brown, JI ^{[1
]}

机构：

[1] Dalhousie Univ, Dept Math Stat & Comp Sci, Halifax, NS B3H 3J5, Canada

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1998年 / 72卷 / 02期

关键词：

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 条

[1]

[Anonymous], 1991, GRAPH THEORY COMBINA

[2]

Barbeau E. J., 1989, Polynomials

[3] IS THE 4-COLOR CONJECTURE ALMOST FALSE [J].

BERAHA, S ;

KAHANE, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (01) :1-12

[4] LIMITS OF CHROMATIC ZEROS OF SOME FAMILIES OF MAPS [J].

BERAHA, S ;

KAHANE, J ;

WEISS, NJ .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (01) :52-65

[5]

BERMAN G, 1969, J COMB THEORY, V6, P301

[6]

BIGGS NL, 1972, J COMB THEORY B, V0012, P00123, DOI [10.1016/0095-8956, DOI 10.1016/0095-8956]

[7] CHROMATIC POLYNOMIALS [J].

BIRKHOFF, GD ;

LEWIS, DC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 60 (NOV) :355-451

[8] LOCATION OF ZEROS OF CHROMATIC AND RELATED POLYNOMIALS OF GRAPHS [J].

BRENTI, F ;

ROYLE, GF ;

WAGNER, DG .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1994, 46 (01) :55-80

[9]

Briggs N., 1993, ALGEBRAIC GRAPH THEO

[10]

BROWN JI, IN PRESS DISCRETE MA

← 1 2 3 →