𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Further results on the lower bounds of mean color numbers

✍ Scribed by F. M. Dong

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
181 KB
Volume
48
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph with n vertices. The mean color number of G, denoted by (G), is the average number of colors used in all n-colorings of G. This paper proves that (G) ! (Q), where Q is any 2-tree with n vertices and G is any graph whose vertex set has an ordering x 1 ,x 2 , . . . ,x n such that x i is contained in a K 3 of G[V i ] for i ΒΌ 3,4, . . . ,n, where V i ΒΌ fx 1 ,x 2 , . . . ,x i g. This result improves two known results that (G) ! (O n ) where O n is the empty graph with n vertices, and (G) ! (T ) where T is a spanning tree of G.

πŸ“œ SIMILAR VOLUMES

A lower bound on the independence number
A lower bound on the independence number of arbitrary hypergraphs
✍ Thiele, Torsten πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 104 KB πŸ‘ 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies Ξ±(H) β‰₯ v∈V f (d

A lower bound on the number of Semi-Bool
A lower bound on the number of Semi-Boolean quadruple systems
✍ Marco Buratti; Alberto Del Fra πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 135 KB πŸ‘ 1 views

## Abstract A Steiner quadruple system of order 2^__n__^ is __Semi‐Boolean__ (SBQS(2^__n__^) in short) if all its derived triple systems are isomorphic to the point‐line design associated with the projective geometry __PG__(__n__βˆ’1, 2). We prove by means of explicit constructions that for any __n__

A lower bound on the number of spanning
A lower bound on the number of spanning trees with k end-vertices
✍ Katherine Heinrich; Guizhen Liu πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 1 views

If a graph G with cycle rank p contains both spanning trees with rn and with n end-vertices, rn < n, then G has at least 2p spanning trees with k end-vertices for each integer k, rn < k < n. Moreover, the lower bound of 2p is best possible. [ l ] and Schuster [4] independently proved that such span