✦ LIBER ✦

Clique polynomials and independent set polynomials of graphs

✍ Scribed by Cornelis Hoede; Xueliang Li

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 492 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90163-5

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces two kinds of graph polynomials, clique polynomial and independent set polynomial.

The paper focuses on expansions of these polynomials. Some open problems are mentioned.

📜 SIMILAR VOLUMES

On graphs with polynomially solvable max

On graphs with polynomially solvable maximum-weight clique problem

✍ Egon Balas; Chang Sung Yu 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB

Tension polynomials of graphs

✍ Martin Kochol 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

The tension polynomial F G (k) of a graph G, evaluating the number of nowhere-zero Z k -tensions in G, is the nontrivial divisor of the chromatic polynomial G (k) of G, in that G (k) ¼ k c(G) F G (k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I G

Partitions of graphs into one or two ind

Partitions of graphs into one or two independent sets and cliques

✍ Andreas Brandstädt 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 417 KB

It is shown in this note that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and one or two cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized

Disjoint cliques and disjoint maximal in

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

✍ Paul Erdös; Arthur M. Hobbs; C. Payan 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 548 KB

Permanental polynomials of graphs

✍ Russell Merris; Kenneth R. Rebman; William Watkins 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 819 KB

Estimates of coefficients of chromatic p

Estimates of coefficients of chromatic polynomials and numbers of cliques of (c,n,m)-graphs

✍ Philippe Pitteloud 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract This paper is mainly concerned with classes of simple graphs with exactly __c__ connected components, __n__ vertices and __m__ edges, for fixed __c,n,m__ ∈ ℕ. We find an optimal lower bound for the __i__th coefficient of the chromatic polynomial of a graph in such a class and also an op