The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial |
| |
Authors: | F M Dong K M Koh |
| |
Institution: | 1. Mathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, , Singapore, Singapore, 637616;2. Department of Mathematics, National University of Singapore, , Singapore, Singapore, 117543 |
| |
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. J Graph Theory |
| |
Keywords: | connectivity chromatic polynomial chromatic zero |
|
|