Legal coloring of graphs (Q1079578)

The following computational problem was initiated by \textit{U. Manber} and \textit{M. Tompa} [Proc. 22nd Annual Symposium on the Foundations of Computer Science (1981)]: Given a graph \(G=(V,E)\) and a real function \(f: V\to {\mathbb{R}}\) which is a proposed vertex coloring. Decide whether f is a proper vertex coloring of G. The elementary steps are taken to be linear comparisons. Using the chromatic polynomial it is proved that for a graph G with m edges the problem of deciding the legality of a vertex coloring of G takes at least \(\sqrt{m/2}\log_ 2m+O(\sqrt{m})\) linear comparisons in the worst case. It is shown how geometric parameters of a space partition associated with G or the number of acyclic orientations of the subgraphs of G influence the complexity of this problem. The author proves also that there exists a unique graph B such that \(| P(G,\lambda)| \geq | P(B_{m,n},\lambda)|\) holds for any integer \(\lambda\) in the set graphs on n vertices with m edges, where P(G,\(\lambda)\) is the chromatic polynomial of G.