Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
| Authors | |
|---|---|
| Year of publication | 2026 |
| Type | Article in Periodical |
| Magazine / Source | ACM Transactions on Computation Theory |
| MU Faculty or unit | |
| Citation | |
| web | https://dl.acm.org/doi/10.1145/3779121 |
| Doi | https://doi.org/10.1145/3779121 |
| Keywords | constraint satisfaction problem; hypergraph colouring; promise problem; topological methods |
| Description | A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, ..., k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the ‘linearly ordered chromatic number’ of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023). |
| Related projects: |