✦ LIBER ✦

New upper bounds for the greatest number of proper colorings of a (V,E)-graph

✍ Scribed by Felix Lazebnik

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 185 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140104

No coin nor oath required. For personal study only.

✦ Synopsis

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 colorings in λ or less colors that a (v, e)‐graph G can have, i.e., f(v, e, λ) = max{P(G; λ): G ∈ 𝒻}. In this paper we determine some new upper bounds for f(v, e, λ).

📜 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

On the greatest number of 2 and 3 colori

On the greatest number of 2 and 3 colorings of a (v, e)-graph

✍ Felix Lazebnik 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

Let 9 denote the family of simple undirected graphs on u vertices having e edges ( ( u , el-graphs) and P(A, G ) be the chromatic polynomial of a graph G. For the given integers u, e, A, let f b , e, A) denote the greatest number of proper colorings in A or less colors that a (u, e)-graph G can have

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

A New Upper Bound on the Cheeger Number

A New Upper Bound on the Cheeger Number of a Graph

✍ Sorin Dragomir; Elisabetta Barletta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o