Legal coloring of graphs (Q1079578)

From MaRDI portal
Revision as of 02:09, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Legal coloring of graphs
scientific article

    Statements

    Legal coloring of graphs (English)
    0 references
    0 references
    1986
    0 references
    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.
    0 references
    proper vertex colouring
    0 references
    chromatic polynomial
    0 references
    acyclic orientation
    0 references
    linear comparisons
    0 references
    open polyhedral set
    0 references
    0 references

    Identifiers