Legal coloring of graphs
type: Item
instance of: scholarly article
title: Legal coloring of graphs
zbMATH Open document ID: 0598.05035
DOI: 10.1007/BF02579408
author: Nathan Linial
published in: Combinatorica
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3963863
zbMATH Keywords: proper vertex colouring
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: acyclic orientation
zbMATH Keywords: linear comparisons
zbMATH Keywords: open polyhedral set
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: On the complexity of computations under varying sets of primitives
cites work: Information Bounds Are Weak in the Shortest Distance Problem
cites work: The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
cites work: On the Polyhedral Decision Problem
cites work: Q3926036
cites work: Acyclic orientations of graphs
cites work: Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
cites work: The Geometry of Root Systems and Signed Graphs
full work available at URL: https://doi.org/10.1007/bf02579408
OpenAlex ID: W2149884907
Recommended article: Q3708830
Recommended article: Q4635974
Recommended article: The coloring of graphs
Recommended article: Linear coloring of graphs
Recommended article: Indicated coloring of graphs
Recommended article: Sur le coloriage des graphs
Recommended article: Q3059317
Recommended article: Q4857375
description: scientific article; zbMATH DE number 3963863