✦ LIBER ✦

Chromatic polynomials and ?-polynomials

✍ Scribed by Wakelin, C. D.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 827 KB
Volume: 22
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199608)22:4<367::aid-jgt10>3.0.co;2-c

No coin nor oath required. For personal study only.

✦ Synopsis

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 the a-polynomial. We obtain necessary and suff icient conditions for this sequence to be symmetrical, and we prove that it is 'skewed' and decreasing beyond its midpoint. We also prove that it is strongly log-concave when G is a complete multipartite graph.

📜 SIMILAR VOLUMES

Cutpoints and the chromatic polynomial

✍ Earl Glen Whitehead Jr.; Lian-Chang Zhao 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 303 KB

## 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 appl

Two Chromatic Polynomial Conjectures

✍ Paul Seymour 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 300 KB

dedicated to professor w. t. tutte on the occasion of his eightieth birthday Let P(\*) be the chromatic polynomial of a graph. We show that P(5) &1 P(6) 2 P(7) &1 can be arbitrarily small, disproving a conjecture of Welsh (and of Brenti, independently) that P(\*) 2 P(\*&1) P(\*+1) and also disprovi

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.

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

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

A Matrix Method for Chromatic Polynomial

A Matrix Method for Chromatic Polynomials

✍ Norman Biggs 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 111 KB

The chromatic polynomials of certain families of graphs can be expressed in terms of the eigenspaces of a linear operator. The operator is represented by a matrix, which is referred to here as the compatibility matrix. In this paper complete sets of eigenfunctions are obtained for several related fa