Přehled o publikaci
2024
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
FILAKOVSKÝ, Marek; Tamio-Vesa NAKAJIMA; Jakub OPRSAL; Gianluca TASINATO; Uli WAGNER et. al.Basic information
Original name
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Authors
FILAKOVSKÝ, Marek; Tamio-Vesa NAKAJIMA; Jakub OPRSAL; Gianluca TASINATO and Uli WAGNER
Edition
Clermont-Ferrand, France, 41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024, p. 1-19, 19 pp. 2024
Publisher
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS
Other information
Language
English
Type of outcome
Proceedings paper
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
Publication form
electronic version available online
Organization
Fakulta informatiky – Repository – Repository
ISBN
978-3-95977-311-9
ISSN
UT WoS
001300393400034
EID Scopus
2-s2.0-85187781179
Keywords in English
constraint satisfaction problem; hypergraph colouring; promise problem; topological methods
Links
CZ.02.01.01/00/22_010/0003229, interní kód Repo. EH22_010/0003229, research and development project.
Changed: 4/4/2025 00:50, RNDr. Daniel Jakubík
Abstract
V originále
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).
