Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
| Autoři | |
|---|---|
| Rok publikování | 2026 |
| Druh | Recenzovaný odborný článek |
| Časopis / Zdroj | ACM Transactions on Computation Theory |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://dl.acm.org/doi/10.1145/3779121 |
| Doi | https://doi.org/10.1145/3779121 |
| Klíčová slova | constraint satisfaction problem; hypergraph colouring; promise problem; topological methods |
| Popis | 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). |
| Související projekty: |