Linearly ordered colourings of hypergraphs

Journal article

A linearly ordered (LO) 𝑘-colouring of an 𝑟-uniform hypergraph assigns an integer from {1, . . . , 𝑘} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for 𝑟 = 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 𝑘-colouring with 𝑘 = 𝑂( 3 √︁ 𝑛 log log𝑛/log𝑛). Second, given an 𝑟-uniform hypergraph that admits an LO 2-colouring, we establish NP-hardness of finding an LO 𝑘-colouring for every constant uniformity 𝑟 ≥ 𝑘 + 2. In fact, we determine relationships between polymorphism minions for all uniformities 𝑟 ≥ 3, which reveals a key difference between 𝑟 < 𝑘 + 2 and 𝑟 ≥ 𝑘 + 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 𝑘-colouring for LO ℓ-colourable 𝑟-uniform hypergraphs for 2 ≤ ℓ ≤ 𝑘 and 𝑟 ≥ 𝑘 − ℓ + 4.

Authors: Nakajima, T-V; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computation Theory
• Volume: 14
• Issue: 3-4
• Pages: 1–19
• Publication date: 2022-11-23
• Acceptance date: 2022-11-01
• DOI: 10.1145/3570909
• EISSN: 1942-3462
• ISSN: 1942-3454
• Language: English
• Keywords: FFR