✦ LIBER ✦

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

✍ Scribed by Felix Lazebnik

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 446 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130207

No coin nor oath required. For personal study only.

✦ Synopsis

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, i.e., f(u, e, A) =' max{P(A, G): G E 9}. In this paper we determine f(u, e, 2) and describe all graphs G for which P(2, G ) = f(u, e, 2). For f(u, e, 3). a lower bound and an upper bound are found. *This paper forms 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

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

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 Number of 3-Edge Colorings of Cub

On the Number of 3-Edge Colorings of Cubic Graphs

✍ Christian Szegedy 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

On the geodetic number of a graph

✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

The Crossing Number of a Graph on a Comp

The Crossing Number of a Graph on a Compact 2-Manifold

✍ F. Shahrokhi; O. Sýkora; L.A. Székely; I. Vrťo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 478 KB

We introduce a general framework to estimate the crossing number of a graph on a compact 2-manifold in terms of the crossing number of the complete graph of the same size on the same manifold. The bounds are tight within a constant multiplicative factor for many graphs, including hypercubes, some co

Chromatic Number and the 2-Rank of a Gra

Chromatic Number and the 2-Rank of a Graph

✍ C.D. Godsil; Gordon F. Royle 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We show that if the adjacency matrix of a graph X has 2-rank 2r, then the chromatic number of X is at most 2 r +1, and that this bound is tight. 2001