---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22247'
abstract:
- lang: eng
text: "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).\r\nHere, 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)."
acknowledgement: "This research was supported by the Charles University project PRIMUS/21/SCI/014,
by the Ministry of Education, Youth\r\nand Sports of the Czech Republic under the
project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229), and by the\r\nAustrian
Science Fund (FWF project P31312-N35). This research was funded by UKRI EP/X024431/1
and by a Clarendon\r\nFund Scholarship. This project has received funding from the
European Union’s Horizon 2020 research and innovation\r\nprogramme under the Marie
Skłodowska-Curie Grant Agreement No 101034413.\r\n"
article_number: '10'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Tamio Vesa
full_name: Nakajima, Tamio Vesa
last_name: Nakajima
- first_name: Jakub
full_name: Opršal, Jakub
id: ec596741-c539-11ec-b829-c79322a91242
last_name: Opršal
orcid: 0000-0003-1245-3456
- first_name: Gianluca
full_name: Tasinato, Gianluca
id: 0433290C-AF8F-11E9-A4C7-F729E6697425
last_name: Tasinato
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly
ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Transactions
on Computation Theory. 2026;18(2). doi:10.1145/3779121
apa: Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U.
(2026). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.
ACM Transactions on Computation Theory. Association for Computing Machinery.
https://doi.org/10.1145/3779121
chicago: Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato,
and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform
Hypergraphs.” ACM Transactions on Computation Theory. Association for Computing
Machinery, 2026. https://doi.org/10.1145/3779121.
ieee: M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” ACM
Transactions on Computation Theory, vol. 18, no. 2. Association for Computing
Machinery, 2026.
ista: Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2026. Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Transactions
on Computation Theory. 18(2), 10.
mla: Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable
3-Uniform Hypergraphs.” ACM Transactions on Computation Theory, vol. 18,
no. 2, 10, Association for Computing Machinery, 2026, doi:10.1145/3779121.
short: M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, ACM Transactions
on Computation Theory 18 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:37Z
date_published: 2026-05-04T00:00:00Z
date_updated: 2026-07-06T09:06:29Z
day: '04'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1145/3779121
ec_funded: 1
external_id:
arxiv:
- '2312.12981'
file:
- access_level: open_access
checksum: 0399ab94085878fc810084845eabd627
content_type: application/pdf
creator: dernst
date_created: 2026-07-06T09:03:02Z
date_updated: 2026-07-06T09:03:02Z
file_id: '22252'
file_name: 2026_TransactionsGraphics_Filakovsky.pdf
file_size: 941518
relation: main_file
success: 1
file_date_updated: 2026-07-06T09:03:02Z
has_accepted_license: '1'
intvolume: ' 18'
issue: '2'
keyword:
- Constraint satisfaction problem
- hypergraph colouring
- promise problem
- topological methods
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: ACM Transactions on Computation Theory
publication_identifier:
eissn:
- 1942-3462
issn:
- 1942-3454
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '15168'
relation: earlier_version
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 18
year: '2026'
...