Please use this identifier to cite or link to this item: https://doi.org/10.1002/jgt.20614
Title: The 3-connectivity of a graph and the multiplicity of zero "2" of its chromatic polynomial
Authors: Dong, F.M.
Koh, K.M. 
Keywords: chromatic polynomial
chromatic zero
connectivity
Issue Date: Jul-2012
Citation: Dong, F.M., Koh, K.M. (2012-07). The 3-connectivity of a graph and the multiplicity of zero "2" of its chromatic polynomial. Journal of Graph Theory 70 (3) : 262-283. ScholarBank@NUS Repository. https://doi.org/10.1002/jgt.20614
Abstract: 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.
Source Title: Journal of Graph Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/104247
ISSN: 03649024
DOI: 10.1002/jgt.20614
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

47
checked on Dec 7, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.