𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by F. M. Dong; K. M. Koh

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
691 KB
Volume
70
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 Supported by NIE AcRf funding (RI 5/06 DFM) of Singapore. Journal of Graph Theory ᭧ 2011 Wiley Periodicals, Inc.

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,

📜 SIMILAR VOLUMES

A Symmetric Function Generalization of t
A Symmetric Function Generalization of the Chromatic Polynomial of a Graph
✍ R.P. Stanley 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 932 KB

For a finite graph \(G\) with \(d\) vertices we define a homogeneous symmetric function \(X_{4 ;}\) of degree \(d\) in the variables \(x_{1}, x_{2}, \ldots\). If we set \(x_{1}=\cdots=x_{n}=1\) and all other \(x_{t}=0\), then we obtain \(Z_{1}(n)\), the chromatic polynomial of (; evaluated at \(n\).

Chromatic Number and the 2-Rank of a Gra
Chromatic Number and the 2-Rank of a Graph
✍ C.D. Godsil; Gordon F. Royle 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We show that if the adjacency matrix of a graph X has 2-rank 2r, then the chromatic number of X is at most 2 r +1, and that this bound is tight. 2001

On the chromatic number of multiple inte
On the chromatic number of multiple interval graphs and overlap graphs
✍ A. Gyárfás 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Let x(G) and o(G) denote the chromatic number and clique number of a graph G. We prove that x can be bounded by a function of o for two well-known relatives of interval graphs. Multiple interval graphs (the intersection graphs of sets which can be written as the union of t closed intervals of a line

The rainbow connectivity of a graph
The rainbow connectivity of a graph
✍ Gary Chartrand; Garry L. Johns; Kathleen A. McKeon; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB