Linearly ordered colourings of hypergraphs

DOI10.1145/3570909MaRDI QIDQ7023432zbMATH OpenFDO

Authors Tamio-Vesa Nakajima, S. Zivny

Publication date 21 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3570909

zbMATH Keywords

algebraic approachhypergraph colouringsminionsPCSPpolymorphismspromise constraint satisfaction

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• (2+)-Sat is NP-hard
• A better performance guarantee for approximate graph coloring
• Algebraic Approach to Promise Constraint Satisfaction
• Approximate coloring of uniform hypergraphs
• Approximate graph coloring by semidefinite programming
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Combinatorial gap theorem and reductions between promise CSPs
• Conditional Hardness for Approximate Coloring
• Graph unique-maximum and conflict-free colorings
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
• Improved hardness of approximating chromatic number
• Improved Inapproximability of Rainbow Coloring
• Improving the performance guarantee for approximate graph coloring
• Introduction to algorithms.
• Linearly ordered colourings of hypergraphs
• New approximation algorithms for graph coloring
• New hardness results for graph and hypergraph colorings
• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On the hardness of approximating the chromatic number
• On the power of unique 2-prover 1-round games
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Rainbow coloring hardness via low sensitivity polymorphisms
• Strong inapproximability results on balanced rainbow-colorable hypergraphs
• The approximability of constraint satisfaction problems
• The Complexity of Near-Optimal Graph Coloring
• The complexity of promise SAT on non-Boolean domains
• The hardness of 3-uniform hypergraph coloring
• The Quest for Strong Inapproximability Results with Perfect Completeness
• The wonderland of reflections
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

Cited in

(10)

• Solving promise equations over monoids and groups
• Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
• A logarithmic approximation of linearly-ordered colourings
• Approximate graph coloring and the crystal with a hollow shadow
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• On the complexity of symmetric vs. functional PCSPs
• Solving promise equations over monoids and groups
• Improved linearly ordered colorings of hypergraphs via SDP rounding
• Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs

This page was built for publication: Linearly ordered colourings of hypergraphs

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