Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, Uli Wagner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Downloads (Pure)

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 languageEnglish
Title of host publication41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
EditorsOlaf Beyersdorff , Mamadou Moustapha Kanté, Orna Kupferman, Daniel Lokshtanov
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages34:1-34:19
Number of pages19
ISBN (Electronic)9783959773119
DOIs
Publication statusPublished - 11 Mar 2024
Event41st International Symposium on Theoretical Aspects of Computer Science - Clermont-Ferrand, France
Duration: 12 Mar 202414 Mar 2024

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik
Volume289
ISSN (Electronic)1868-8969

Conference

Conference41st International Symposium on Theoretical Aspects of Computer Science
Abbreviated titleSTACS 2024
Country/TerritoryFrance
CityClermont-Ferrand
Period12/03/2414/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

Fingerprint

Dive into the research topics of 'Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs'. Together they form a unique fingerprint.

Cite this