✦ LIBER ✦

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

✍ Scribed by Philippe Pitteloud

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 134 KB
Volume: 42
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10039

No coin nor oath required. For personal study only.

✦ Synopsis

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 optimal upper bound for the number of j‐cliques contained in such a graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 81–94, 2003

📜 SIMILAR VOLUMES

Numbers of cubic graphs

✍ R. W. Robinson; N. C. Wormald 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB

## Abstract The numbers of unlabeled cubic graphs on __p = 2n__ points have been found by two different counting methods, the best of which has given values for __p ≦__ 40.

D. Liu and X. Zhu, Erratum to: “Fraction

D. Liu and X. Zhu, Erratum to: “Fractional chromatic number and circular chromatic number for distance graphs with large clique size”. Journal of Graph Theory47(2) 2004, 129–146

✍ Daphne Der-Fen Liu; Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 45 KB

## Abstract The original article to which this Erratum refers was published in Journal of Graph Theory 47:129–146,2004.

Subgraphs of large connectivity and chro

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

✍ N. Alon; D. Kleitman; C. Thomassen; M. Saks; P. Seymour 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

For each pair k, rn of natural numbers there exists a natural number f(k, rn) such that every f ( k , m)-chromatic graph contains a k-connected subgraph of chromatic number at least rn.

Estimation of the Energies of N–N and C–

Estimation of the Energies of N–N and C–C Interactions in F.C.C. Fe–N and Fe–C Alloys on the Basis of Mössbauer Spectroscopy Data

✍ A. G. Balanyuk; V. N. Bugaev; V. M. Nadutov; A. L. Sozinov 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB 👁 2 views

1-Factorizations of random regular graph

1-Factorizations of random regular graphs

✍ M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 2 views

It is shown that for each r G 3, a random r-regular graph on 2 n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2 n vertices, as n ª ϱ. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almo

On the chromatic number of a random 5-re

On the chromatic number of a random 5-regular graph

✍ J. Díaz; A. C. Kaporis; G. D. Kemkes; L. M. Kirousis; X. Pérez; N. Wormald 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 275 KB 👁 1 views

## Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is as