✦ LIBER ✦

A Symmetric Function Generalization of the Chromatic Polynomial of a Graph

✍ Scribed by R.P. Stanley

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 932 KB
Volume: 111
Category: Article
ISSN: 0001-8708
DOI: 10.1006/aima.1995.1020

No coin nor oath required. For personal study only.

✦ Synopsis

For a finite graph (G) with (d) vertices we define a homogeneous symmetric function (X_{4 ;}) of degree (d) in the variables (x_{1}, x_{2}, \ldots). If we set (x_{1}=\cdots=x_{n}=1) and all other (x_{t}=0), then we obtain (Z_{1}(n)), the chromatic polynomial of (; evaluated at (n). We consider the expansion of (X_{6}), in terms of various symmetric function bases. The coefficients in these expansions are related to partitions of the vertices into stable subsets, the Möbius function of the lattice of contractions of (G), and the structure of the acyclic orientations of (G). The coefficients which atrise when (\lambda_{\text {, }}), is expanded in terms of elementary symmetric functions are particularly interesting. and for cerlain graphs are related to the theory of Hecke algebras and Kazhdan Lusztig polynomials. ' 1995 Academic Press. Inc.

📜 SIMILAR VOLUMES

A generalization of chromatic index

✍ E. Sampathkumar; G.D. Kamath 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 261 KB

Let G = (V, E) be a graph and k > 2 an integer. The general chromatic index x;(G) of G is the minimum order of a partition P of E such that for any set F in P every component in the subgraph (F) induced by F has size at most k-1. This paper initiates a study of x;(G) and generalizes some known resul

On σ-polynomials and a class of chromati

On σ-polynomials and a class of chromatically unique graphs

✍ Qingyan Du 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 655 KB

Du, Q., On o-polynomials and a class of chromatically unique graphs, Discrete Mathematics 115 (1993) 153-165. Let cr(G)=C:,,aicr '-' be the u-polynomial of a graph G. We ask the question: When k and a, are given, what is the largest possible value of ai(O < i < k) for any graph G? In this paper, thi

Chromatic factorizations of a graph

✍ S. Louis Hakimi; Edward F. Schmeichel 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

Let n, 2 n2 L . . B n, 2 2 be integers. We say that G has an (n,, n2, , . , , n,)-chromatic factorization if G can be edge-factored as G, @ G2 @ + . . @ G, with x ( G , ) = n,, for i = 1,2, . . . , k . The following results are proved : then K,, has an (n,, n2,, . , , n,)-chromatic factorization. W

Generalizations of independence and chro

Generalizations of independence and chromatic numbers of a graph

✍ E. Sampathkumar 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 426 KB

Sampathkumar, E., Generalizations of independence and chromatic numbers of a graph, Discrete Mathematics 115 (1993) 2455251. Let G = (V, E) be a graph and k > 2 be an integer. A set S c V is k-independent if every component in the subgraph (S) induced by S has order at most k-1. The general chromati

The Wiener polynomial of a graph

✍ Bruce E. Sagan; Yeong-Nan Yeh; Ping Zhang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 674 KB

The Wiener index is a graphical invariant that has found extensive application in chemistry. We define a generating function, which we call the Wiener polynomial, whose derivative is a q-analog of the Wiener index. We study some of the elementary properties of this polynomial and compute it for some

The 3-connectivity of a graph and the mu

The 3-connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

✍ F. M. Dong; K. M. Koh 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 691 KB

Let G be a graph of order n, maximum degree , and minimum degree . Let P(G, ) be the chromatic polynomial of G. It is known that the multiplicity of zero "0" of P(G, ) is one if G is connected, and the multiplicity of zero "1" of P(G, ) is one if G is 2-connected. Is the multiplicity of zero "2" of