Publication details
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Proceedings |
| Conference | 41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 |
| MU Faculty or unit | |
| Citation | |
| web | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34 |
| Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2024.34 |
| Keywords | constraint satisfaction problem; hypergraph colouring; promise problem; topological methods |
| Attached files | |
| 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). |
| Related projects: |