Legal coloring of graphs

DOI10.1007/BF02579408zbMath0598.05035OpenAlexW2149884907MaRDI QIDQ1079578

Nathan Linial

Publication date: 1986

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579408

zbMATH Keywords

chromatic polynomialacyclic orientationproper vertex colouringlinear comparisonsopen polyhedral set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Counting dominating sets and related structures in graphs ⋮ A bibliography on chromatic polynomials ⋮ A proof of Tomescu's graph coloring conjecture ⋮ Maximizing proper colorings on graphs ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ An Extremal Property of Turán Graphs, II ⋮ Extremal Graphs for Homomorphisms II ⋮ Optimal graphs for chromatic polynomials ⋮ Unnamed Item ⋮ On the complexity of distributed graph coloring with local minimality constraints ⋮ Extremal graphs for homomorphisms ⋮ The maximum number of colorings of graphs of given order and size: a survey ⋮ Maximum number of colourings: 4-chromatic graphs ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ Counting colorings of a regular graph

Cites Work

• On the complexity of computations under varying sets of primitives
• Acyclic orientations of graphs
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• On the Polyhedral Decision Problem
• The Geometry of Root Systems and Signed Graphs
• Information Bounds Are Weak in the Shortest Distance Problem
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Unnamed Item

This page was built for publication: Legal coloring of graphs