Abstract
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).
| Original language | English |
|---|---|
| Title of host publication | 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) |
| Editors | Olaf Beyersdorff , Mamadou Moustapha Kanté, Orna Kupferman, Daniel Lokshtanov |
| Place of Publication | Dagstuhl, Germany |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Pages | 34:1-34:19 |
| Number of pages | 19 |
| ISBN (Electronic) | 9783959773119 |
| DOIs | |
| Publication status | Published - 11 Mar 2024 |
| Event | 41st International Symposium on Theoretical Aspects of Computer Science - Clermont-Ferrand, France Duration: 12 Mar 2024 → 14 Mar 2024 |
Publication series
| Name | Leibniz International Proceedings in Informatics (LIPIcs) |
|---|---|
| Publisher | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Volume | 289 |
| ISSN (Electronic) | 1868-8969 |
Conference
| Conference | 41st International Symposium on Theoretical Aspects of Computer Science |
|---|---|
| Abbreviated title | STACS 2024 |
| Country/Territory | France |
| City | Clermont-Ferrand |
| Period | 12/03/24 → 14/03/24 |
Bibliographical note
Funding:Marek Filakovský: This research was supported by Charles University (project PRIMUS/ 21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229).
Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper.
Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).
Keywords
- constraint satisfaction problem
- hypergraph colouring
- promise problem
- topological methods