✦ LIBER ✦

Some corollaries of a theorem of Whitney on the chromatic polynomial

✍ Scribed by Felix Lazebnik

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 749 KB
Volume: 87
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90070-i

No coin nor oath required. For personal study only.

✦ Synopsis

Lazebnik, F., Some corollaries of a theorem of Whitney on the chromatic polynomial, Discrete Mathematics 87 (1991) 53-64.

Let 9 denote the family of simple undirected graphs on u vertices having e edges, P(G; A) be the chromatic polynomial of a graph G. For the given integers v, e, A, let f(v, e, A) = max{P(G; A): G E S}. In this paper we determine some lower and upper bounds forf(u, e, A) provided that I is sufficiently large. In some casesf(u, e, A) is found and all graphs G for which P(G; n) =f(u, e, ,I) are described. Connections between these problems and some other questions from the extremal graph theory are analysed using Whitney's characterization of the coefficients of P(G; A) in terms of the number of 'broken circuits' in G. *This paper is based on a part of a Ph.D. Thesis written by the author under the supervision of Prof. H.S. Wilf at the University of Pennsylvania.

📜 SIMILAR VOLUMES

On the Roots of Chromatic Polynomials

✍ Jason I. Brown 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 158 KB

It is proved that the chromatic polynomial of a connected graph with n vertices and m edges has a root with modulus at least (m&1)Â(n&2); this bound is best possible for trees and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a

Some Theorems Concerning the Star Chroma

Some Theorems Concerning the Star Chromatic Number of a Graph

✍ Bing Zhou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 379 KB

We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number. 1997 Academic Press /\*(G)=inf { m d : G has an (m, d )&coloring = . article no. TB961738 245 0095-8956Â97 25.00

A theorem on the factorization of matrix

A theorem on the factorization of matrix polynomials

✍ J. Maroulas 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 363 KB

A constructive proof of a Whitney extens

A constructive proof of a Whitney extension theorem in one variable

✍ J.C Archer; E Le Gruyer 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 684 KB

Note on isomorphic hypergraphs and some

Note on isomorphic hypergraphs and some extensions of Whitney's theorem to families of sets

✍ C Berge; R Rado 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 667 KB

A Symmetric Function Generalization of t

A Symmetric Function Generalization of the Chromatic Polynomial of a Graph

✍ R.P. Stanley 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 932 KB

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\).