✦ LIBER ✦

Expansions of the chromatic polynomial

✍ Scribed by Norman Biggs

Publisher: Elsevier Science
Year: 1973
Tongue: English
Weight: 739 KB
Volume: 6
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(73)90040-x

No coin nor oath required. For personal study only.

✦ Synopsis

The chromatic polynomial ;X chromial) of a graph was first defined by Birkhoff in 1912, ;md gives the number of ways or" properly colov iing the vertices of the graph with any number of colours. A good survey of the b-sic facts about these polynomials may be found in the article by Read [ 3 3 .

It has recently been noticed that some classical problems of physics can be expressed in terms of chromials, and papers by Nagle 12 1, Baker [ 1 ] , Temperley and Lieb [4], are concerned with methods of expanding the chromial for use in such problems. In this note we shall unify. simplify, and generalise their treatments, confining our attention to the theoretical basis of the methods.

Y(E,3W VIE,) = vr,

W(E,)n V(E2)I=Oor 1.

📜 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

The limit of chromatic polynomials

✍ D Kim; I.G Enting 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 639 KB

The chromatic polynomial of an unlabeled

The chromatic polynomial of an unlabeled graph

✍ P Hanlon 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 615 KB

Coefficients of chromatic polynomials

✍ G.H.J Meredith 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 129 KB

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

Proof of a Chromatic Polynomial Conjectu

Proof of a Chromatic Polynomial Conjecture

✍ F.M. Dong 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 138 KB

Let P(G, \*) denote the chromatic polynomial of a graph G. It is proved in this paper that for every connected graph G of order n and real number \* n, (\*&2) n&1 P(G, \*)&\*(\*&1) n&2 P(G, \*&1) 0. By this result, the following conjecture proposed by Bartels and Welsh is proved: P(G, n)(P(G, n&1))