𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Correlation decay and deterministic FPTAS for counting colorings of a graph

✍ Scribed by David Gamarnik; Dmitriy Katz

Book ID
113699032
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
333 KB
Volume
12
Category
Article
ISSN
1570-8667

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Some new bounds for the maximum number o
Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
✍ Byer, Owen D. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 126 KB πŸ‘ 3 views

Let f (v, e, Ξ») denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in Ξ» colors. In this paper we present some new upper bounds for f (v, e, Ξ»). In particular, a new notion of pseudoproper colorings of a graph is given, which allows us to significantly improve

New upper bounds for the greatest number
New upper bounds for the greatest number of proper colorings of a (V,E)-graph
✍ Felix Lazebnik πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 185 KB

## Abstract Let 𝒻 denote the family of simple undirected graphs on __v__ vertices having __e__ edges ((__v__, __e__)‐graphs) and __P__(__G__; Ξ») be the chromatic polynomial of a graph __G.__ For the given integers __v__, __e__, and Ξ», let __f__(__v__, __e__, Ξ») denote the greatest number of proper