Bounds for mean colour numbers of graphs

Let μ(G) denote the mean colour number of a graph G. Mosca discovered some counterexamples which disproved a conjecture proposed by Bartels and Welsh that if H is a subgraph of G, then μ(H)⩽μ(G). In this paper, we show that this conjecture holds under the condition that either G is a chordal graph or H is a graph which can be obtained from a tree by replacing a vertex by a clique. This result gives a method to find upper bounds and lower bounds for the mean colour number of any graph. We also prove that μ(G)<μ(G∪K1) for an arbitrary graph G.