✦ LIBER ✦

Cutpoints and the chromatic polynomial

✍ Scribed by Earl Glen Whitehead Jr.; Lian-Chang Zhao

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 303 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080305

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that the multiplicity of the root 1 in the chromatic polynomial of a simple graph G is equal to the number of nontrivial blocks in G. In particular, a connected simple graph G has a cutpoint if and only if its chromatic polynomial is divisible by (λ – 1)^2^. We apply this theorem to obtain some chromatic equivalence and uniqueness results.

📜 SIMILAR VOLUMES

Chromatic polynomials and ?-polynomials

✍ Wakelin, C. D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 827 KB

In this paper we present some results on the sequence of coefficients of the chromatic polynomial of a graph relative to the complete graph basis, that is, when it is expressed as the sum of the chromatic polynomials of complete graphs. These coefficients are the coefficients of what is often called

On the Roots of Chromatic Polynomials

✍ Jason I. Brown 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 158 KB

It is proved that the chromatic polynomial of a connected graph with n vertices and m edges has a root with modulus at least (m&1)Â(n&2); this bound is best possible for trees and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a

Chromatic polynomials, polygon trees, an

Chromatic polynomials, polygon trees, and outerplanar graphs

✍ C. D. Wakelin; D. R. Woodall 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB

## Abstract It is proved that all classes of polygon trees are characterized by their chromatic polynomials, and a characterization is given of those polynominals that are chromatic polynomials of outerplanar graphs. The first result yields an alternative proof that outerplanar graphs are recogniza

Chromatic polynomials and whitney's brok

Chromatic polynomials and whitney's broken circuits

✍ Ruth A. Bari; Dick Wick Hall 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

## Abstract The theorem of Hassler Whitney, which gives the chromatic polynomial of a graph in terms of “broken circuits,” is used to derive a new formula for the coefficients of chromatic polynomials.

Lower bounds and upper bounds for chroma

Lower bounds and upper bounds for chromatic polynomials

✍ Klaus Dohmen 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB

## Abstract In this paper we give lower bounds and upper bounds for chromatic polynomials of simple undirected graphs on __n__ vertices having __m__ edges and girth exceeding __g__ © 1993 John Wiley & Sons, Inc.

A Correlation Inequality Involving Stabl

A Correlation Inequality Involving Stable Set and Chromatic Polynomials

✍ G.E. Farr 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Suppose each vertex of a graph \(G\) is chosen with probability \(p\), these choices being independent. Let \(A(G, p)\) be the probability that no two chosen vertices are adjacent. This is essentially the clique polynomial of the complement of \(G\) which has been extensively studied in a variety of