Abstract
A linearly ordered (LO) kcolouring of an runiform hypergraph assigns an integer from {1, …, k} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for r = 3, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic nonmonochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied LO colourings on 3uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results.
First, given a 3uniform hypergraph that admits an LO 2colouring, one can find in polynomial time an LO kcolouring with k = O(√{nlog log n}/log n), where n is the number of vertices of the input hypergraph. This is established by building on ideas from algorithms designed for approximate graph colourings.
Second, given an runiform hypergraph that admits an LO 2colouring, we establish NPhardness of finding an LO 3colouring for every constant uniformity r ≥ 5. In fact, we determine the precise relationship of polymorphism minions for all uniformities r ≥ 3, which reveals a key difference between r = 3,4 and r ≥ 5 and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NPhardness of finding an LO (k+1)colouring for LO kcolourable runiform hypergraphs for k ≥ 2 and r ≥ 5.
BibTeX  Entry
@InProceedings{nakajima_et_al:LIPIcs.ICALP.2022.128,
author = {Nakajima, TamioVesa and \v{Z}ivn\'{y}, Stanislav},
title = {{Linearly Ordered Colourings of Hypergraphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {128:1128:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16469},
URN = {urn:nbn:de:0030drops164692},
doi = {10.4230/LIPIcs.ICALP.2022.128},
annote = {Keywords: hypegraph colourings, promise constraint satisfaction, PCSP, polymorphisms, minions, algebraic approach}
}
Keywords: 

hypegraph colourings, promise constraint satisfaction, PCSP, polymorphisms, minions, algebraic approach 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 