Further results on the lower bounds of mean color numbers

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  = { x 1 , x 2 ,…, x i }. 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 . © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005