✦ LIBER ✦

Chromatic polynomials of hypergraphs

✍ Scribed by Ewa Drgas-Burchardt; Ewa Łazuka

Publisher: Elsevier Science
Year: 2007
Tongue: English
Weight: 182 KB
Volume: 20
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2007.02.006

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a natural generalization of the chromatic polynomial of a graph. Let the symbol f (x 1 ,...,x m ) (H, λ) denote a number of different λ-colourings of a hypergraph H = (X, E), where X = {v 1 , . . . , v n } and E = {e 1 , . . . , e m }, satisfying that in an edge e i there are used at least x i different colours. In the work we show that f (x 1 ,...,x m ) (H, λ) can be expressed by a polynomial in λ of degree n and as a sum of graph chromatic polynomials. Moreover, we present a reduction formula for calculating f (x 1 ,...,x m ) (H, λ). It generalizes the similar formulas observed by H. Whitney and R.P. Jones for standard colourings of graphs and hypergraphs respectively. We also study some coefficients of f (x 1 ,...,x m ) (H, λ) and their connection with the sizes of the edges of H.

📜 SIMILAR VOLUMES

Chromatic polynomials and ?-polynomials

✍ Wakelin, C. D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 827 KB

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 chromatic numbers of random hypergra

The chromatic numbers of random hypergraphs

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

For a pair of integers 1 F ␥r, the ␥-chromatic number of an r-uniform Ž . hypergraph H s V, E is the minimal k, for which there exists a partition of V into subsets < < T, . . . , T such that e l T F ␥ for every e g E. In this paper we determine the asymptotic 1 k i Ž . behavior of the ␥-chromatic n

Chromatic Coefficients of Linear Uniform

Chromatic Coefficients of Linear Uniform Hypergraphs

✍ Ioan Tomescu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 224 KB

Ultimate chromatic polynomials

✍ Nigel Ray; William Schmitt 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 844 KB

We outline an approach to enumeration problems which relies on the algebra of free abelian groups, giving as our main application a generalisation of the chromatic polynomial of a simple graph G. Our polynomial lies in the free abelian group generated by the poset K(G) of contractions of G, and redu

Generalized chromatic polynomials

✍ David Joyce 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 739 KB

T-chromatic polynomials

✍ Ian Robertson 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 463 KB

Given a set T of nonnegative integers, a T-coloring of a graph G is a labeling of the vertices of G with positive integers such that no pair of adjacent vertices is labeled with integers differing by a number in T. Let Tc(,l) denote the number of ways to T-color G with numbers from the set (LZ..., A