Linearly ordered colourings of hypergraphs

DOI10.1145/3570909arXiv2204.05628MaRDI QIDQ6396281FDOQ6396281

Authors: Tamio-Vesa Nakajima, S. Zivny 

Publication date: 12 April 2022

Abstract: A linearly ordered (LO) $k$-colouring of an $r$-uniform hypergraph assigns an integer from $1,ldots,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 non-monochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied LO colourings on $3$-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results. First, given a 3-uniform hypergraph that admits an LO $2$-colouring, one can find in polynomial time an LO $k$-colouring with $k=O(sqrt[3]nloglogn/logn)$. Second, given an $r$-uniform hypergraph that admits an LO $2$-colouring, we establish NP-hardness of finding an LO $k$-colouring for every constant uniformity $rgeqk+2$. In fact, we determine relationships between polymorphism minions for all uniformities $rgeq3$, which reveals a key difference between $r<k+2$ and $rgeqk+2$ and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NP-hardness of finding an LO $k$-colouring for LO $ell$-colourable $r$-uniform hypergraphs for $2leqellleqk$ and $rgeqk-ell+4$.

This page was built for publication: Linearly ordered colourings of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396281)