Citation
N. Alon et M. Tarsi, A NOTE ON GRAPH COLORINGS AND GRAPH POLYNOMIALS, J COMB TH B, 70(1), 1997, pp. 197-201
Citations number
5
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
70
Issue
1
Year of publication
1997
Pages
197 - 201
Database
ISI
SICI code
0095-8956(1997)70:1<197:ANOGCA>2.0.ZU;2-C
Abstract
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) = Pi(ij is an eleme
nt of E,t<j) (c(1) - x(j)) lies in certain ideals. We describe a short
proof of this result, using Ore's version of Hajos' theorem. We also
show that a certain weighted sum over the proper k-colorings of a grap
h can be computed from its graph polynomial in a simple manner. (C) 19
97 Academic Press.