TY - UNPB
T1 - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
AU - Filakovský, Marek
AU - Nakajima, Tamio-Vesa
AU - Opršal, Jakub
AU - Tasinato, Gianluca
AU - Wagner, Uli
N1 - accepted to STACS 2024 (Track A)
PY - 2023/12/20
Y1 - 2023/12/20
N2 - A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1, \dots, 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\v{s}al, Wrochna, and \v{Z}ivn\'y (2023).
AB - A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1, \dots, 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\v{s}al, Wrochna, and \v{Z}ivn\'y (2023).
KW - cs.CC
KW - math.AT
KW - math.CO
U2 - 10.48550/arXiv.2312.12981
DO - 10.48550/arXiv.2312.12981
M3 - Preprint
SP - 1
EP - 39
BT - Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
PB - arXiv
ER -