Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek ve sborníku |
| Konference | 41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34 |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2024.34 |
| Klíčová slova | constraint satisfaction problem; hypergraph colouring; promise problem; topological methods |
| Přiložené soubory | |
| 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). |
| Související projekty: |