Premium
The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial
Author(s) -
Dong F. M.,
Koh K. M.
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20614
Subject(s) - multiplicity (mathematics) , mathematics , chromatic polynomial , combinatorics , connectivity , graph , chromatic scale , discrete mathematics , zero (linguistics) , simple graph , geometry , linguistics , philosophy
Let G be a graph of order n , maximum degree Δ, and minimum degree δ. 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 Δ + δ⩾ 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 Δ + δ⩾ n and (Δ, δ 3 )≠( n −3, 3), where δ 3 is the third minimum degree of G , then the multiplicity of zero “2” of P ( G , λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory