Approximate coloring of uniform hypergraphs (extended abstract)

DOI10.1007/3-540-68530-8_40MaRDI QIDQ4252044zbMATH OpenFDO

Authors Michael Krivelevich, Benny Sudakov

Publication date 6 October 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-68530-8_40

zbMATH Keywords

approximation algorithmchromatic numbercoloring \(r\)-uniform hypergraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximate coloring of uniform hypergraphs
• Approximate hypergraph coloring
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• The hardness of 3-uniform hypergraph coloring

Cited in

(26)

• Testing hypergraph colorability
• Flexible coloring
• The existence of uniform hypergraphs for which the interpolation property of complete coloring fails
• Approximability of the upper chromatic number of hypergraphs
• The hardness of 3-uniform hypergraph coloring
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Semi-definite positive programming relaxations for graph K_n-coloring in frequency assignment.
• The complexity of vertex coloring problems in uniform hypergraphs with high degree
• scientific article; zbMATH DE number 1002208 (Why is no real title available?)
• Approximations to m‐Colored Complete Infinite Hypergraphs
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• Approximate hypergraph coloring
• scientific article; zbMATH DE number 1947044 (Why is no real title available?)
• scientific article; zbMATH DE number 1522920 (Why is no real title available?)
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Coloring bipartite hypergraphs
• Approximate coloring of uniform hypergraphs
• Improved bounds and algorithms for hypergraph 2-coloring
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Approximate hypergraph coloring under low-discrepancy and related promises
• The complexity of 2-coloring and strong coloring in uniform hypergraphs with high degrees
• Linearly ordered colourings of hypergraphs
• Edge-coloring of 3-uniform hypergraphs

This page was built for publication: Approximate coloring of uniform hypergraphs (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4252044)