Some corollaries of a theorem of Whitney on the chromatic polynomial (Q2640610): Difference between revisions

A proper \(\lambda\)-colouring of a graph G is a mapping from the vertex set into the set \(\{\) 1,2,...,\(\lambda\}\) such that no two adjacent vertices have the same image. Now P(G,\(\lambda\)) denotes the number of proper \(\lambda\)-colourings of G and is called the chromatic polynomial of G. The following problem was formulated by H. S. Wilf: For given integers v, e, \(\lambda\), let \(f(v,e,\lambda)=\max \{P(G,\lambda): G\in {\mathcal F}\}\) where \({\mathcal F}\) is the family of all simple and undirected graphs on v vertices having e edges. Determine f(v,e,\(\lambda\)). Describe all graphs G with \(f(v,e,\lambda)=P(G,\lambda)\). This paper contains a partial solution. Lower and upper bounds for f(v,e,\(\lambda\)) are determined provided that \(\lambda\) is sufficiently large. Connections between the considered problem and other questions of extremal graph theory are stated.