Legal coloring of graphs
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.
- Acyclic orientations of graphs
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- scientific article; zbMATH DE number 3738914 (Why is no real title available?)
- Information Bounds Are Weak in the Shortest Distance Problem
- On the complexity of computations under varying sets of primitives
- On the Polyhedral Decision Problem
- The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
- The Geometry of Root Systems and Signed Graphs
- A bibliography on chromatic polynomials
- Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
- The number of legal Go positions
- The maximum number of colorings of graphs of given order and size: a survey
- Counting colorings of a regular graph
- A proof of Tomescu's graph coloring conjecture
- Optimal graphs for chromatic polynomials
- Counting dominating sets and related structures in graphs
- On the complexity of distributed graph coloring with local minimality constraints
- Maximizing proper colorings on graphs
- The role of a-priori information in networks of rational agents
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Extremal graphs for homomorphisms
- Extremal H‐Colorings of Graphs with Fixed Minimum Degree
- An Extremal Property of Turán Graphs, II
- Extremal graphs for homomorphisms. II
- Resource efficient stabilization for local tasks despite unknown capacity links
- Maximum number of colourings: 4-chromatic graphs
This page was built for publication: Legal coloring of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079578)
