The 3-connectivity of a graph and the multiplicity of zero "2" of its chromatic polynomial

被引:1
作者
Dong, F. M. [1 ]
Koh, K. M. [2 ]
机构
[1] Nanyang Technol Univ, Natl Inst Educ, Singapore 637616, Singapore
[2] Natl Univ Singapore, Dept Math, Singapore 117543, Singapore
关键词
connectivity; chromatic polynomial; chromatic zero;
D O I
10.1002/jgt.20614
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph of order n, maximum degree ?, and minimum degree d. Let P(G, ?) be the chromatic polynomial of G. It is known that the multiplicity of zero 0 of P(G, ?) is one if G is connected, and the multiplicity of zero 1 of P(G, ?) is one if G is 2-connected. Is the multiplicity of zero 2 of P(G, ?) at most one if G is 3-connected? In this article, we first construct an infinite family of 3-connected graphs G such that the multiplicity of zero 2 of P(G, ?) is more than one, and then characterize 3-connected graphs G with ? + d?n such that the multiplicity of zero 2 of P(G, ?) is at most one. In particular, we show that for a 3-connected graph G, if ? + d?n and (?, d3)?(n-3, 3), where d3 is the third minimum degree of G, then the multiplicity of zero 2 of P(G, ?) is at most one. (c) 2011 Wiley Periodicals, Inc. J Graph Theory
引用
收藏
页码:262 / 283
页数:22
相关论文
共 8 条
[1]  
[Anonymous], CHROMATIC POLYNOMIAL
[3]  
Read R.C., 1968, J. Combin. Theory, V4, P52
[4]  
Read RC., 1988, SELECTED TOPICS GRAP, V3, P15
[5]  
Wakelin C.D., 1994, THESIS U NOTTINGHAM
[6]   CUTPOINTS AND THE CHROMATIC POLYNOMIAL [J].
WHITEHEAD, EG ;
ZHAO, LC .
JOURNAL OF GRAPH THEORY, 1984, 8 (03) :371-377
[7]  
Woodall D.R., 1977, COMBINATORIAL SURVEY, P199
[8]  
Zykov A.A., 1949, Mat. Shornik (N.S.), V24, P163