A logarithmic approximation of linearly-ordered colourings

DOI10.4230/LIPICS.APPROX/RANDOM.2024.7MaRDI QIDQ6920839zbMATH OpenFDO

Authors Johan Hastad, Björn Martinsson, Tamio-Vesa Nakajima, S. Zivny

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.7

zbMATH Keywords

approximationhypergraphlinear ordered colouringpromise constraint satisfaction problems

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• Algebraic Approach to Promise Constraint Satisfaction
• An algorithmic blend of LPs and ring equations for promise CSPs
• Approximate coloring of uniform hypergraphs
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Linearly ordered colourings of hypergraphs
• Linearly ordered colourings of hypergraphs
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• The complexity of temporal constraint satisfaction problems
• The hardness of 3-uniform hypergraph coloring

Cited in

(2)

• 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: A logarithmic approximation of linearly-ordered colourings

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