Further results on the lower bounds of mean color numbers
Fengming Dong · Journal of Graph Theory · 2004
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 x1,x2,…,xn such that xi is contained in a K3 of G[Vi] for i = 3,4,…,n, where Vi = {x1,x2,…,xi}. This result improves two known results that μ(G) ≥ μ(On) where On 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