𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Matrix Method for Chromatic Polynomials

✍ Scribed by Norman Biggs

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
111 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 families, and the results are used to provide information about the location of the zeros of the associated chromatic polynomials. A number of uniform features are observed, and these are explained in terms of general properties of the underlying construction. 2001

πŸ“œ SIMILAR VOLUMES

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))

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.

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.

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