𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Note on Graph Colorings and Graph Polynomials

✍ Scribed by Noga Alon; Michael Tarsi

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
230 KB
Volume
70
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

dedicated to professor w. t. tutte on the occasion of his eightieth birtday

It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using Ore's version of Hajo s' theorem. We also show that a certain weighted sum over the proper k-colorings of a graph can be computed from its graph polynomial in a simple manner. 1997 Academic Press Theorem 1.1 and the two corollaries following it. The proof is based on article no. TB971753 197 0095-8956Γ‚97 25.00

πŸ“œ SIMILAR VOLUMES

On color polynomials of Fibonacci graphs
On color polynomials of Fibonacci graphs
✍ Sherif El-Basil πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 216 KB

A recursion exists among the coefficients of the color polynomials of some of the families of graphs considered in recent work of Balasubramanian and Ramaraj.' Such families of graphs have been called Fibonacci graphs. Application to king patterns of lattices is given. The method described here appl

Note on a new coloring number of a graph
Note on a new coloring number of a graph
✍ P. HorΓ‘k; J. Ε irÑň πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 112 KB πŸ‘ 1 views

## Abstract The distance coloring number __X__~__d__~(__G__) of a graph __G__ is the minimum number __n__ such that every vertex of __G__ can be assigned a natural number __m__ ≀ __n__ and no two vertices at distance __i__ are both assigned __i__. It is proved that for any natural number __n__ ther

A note on defective colorings of graphs
A note on defective colorings of graphs in surfaces
✍ Dan Archdeacon πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 139 KB πŸ‘ 2 views

A graph is (rn, k)-colorable if its vertices can be colored with rn colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen. Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that eve

Path homomorphisms, graph colorings, and
Path homomorphisms, graph colorings, and boolean matrices
✍ Jaroslav NeΕ‘etΕ™il; Claude Tardif πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 124 KB

## Abstract We investigate bounds on the chromatic number of a graph __G__ derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray\*}\vec{P}\end{eqnarray\*}\end{document} into some orientation \documentclass{