Legal coloring of graphs

DOI10.1007/BF02579408MaRDI QIDQ1079578zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 3935075
• Graph colorings
• The coloring of graphs
• Linear coloring of graphs
• Indicated coloring of graphs
• Sur le coloriage des graphs
• Graph coloring problems
• scientific article; zbMATH DE number 821271

Cites work

• scientific article; zbMATH DE number 3738914 (Why is no real title available?)
• Acyclic orientations of graphs
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Information Bounds Are Weak in the Shortest Distance Problem
• On the Polyhedral Decision Problem
• On the complexity of computations under varying sets of primitives
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• The Geometry of Root Systems and Signed Graphs

Cited in

(18)

• The maximum number of colorings of graphs of given order and size: a survey
• A proof of Tomescu's graph coloring conjecture
• The number of legal Go positions
• Optimal graphs for chromatic polynomials
• Counting dominating sets and related structures in graphs
• Maximizing proper colorings on graphs
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Extremal graphs for homomorphisms. II
• A bibliography on chromatic polynomials
• Counting colorings of a regular graph
• Resource efficient stabilization for local tasks despite unknown capacity links
• The role of a-priori information in networks of rational agents
• On the complexity of distributed graph coloring with local minimality constraints
• Extremal H‐Colorings of Graphs with Fixed Minimum Degree
• Maximum number of colourings: 4-chromatic graphs
• An Extremal Property of Turán Graphs, II
• Extremal graphs for homomorphisms
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

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)