Bounds for mean colour numbers of graphs (Q1405125)

Let \(G\) be a graph of order \(n\). For any \(n\)-colouring \(C\) of \(G\) let \(\ell(C)\) denote the actual number of colours used. By the mean colour number \(\mu(G)\) of \(G\) we mean the average of the \(\ell(C)\)'s over all \(n\)-colourings of \(C\). It is shown that if \(H\) is a subgraph of \(G\), then \(\mu(H)\leq \mu(G)\) 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. Some unsolved problems are proposed, too.