3 papers
cs.CC2025
Hardness of 4-Colourings G-Colourable Graphs
Sergey Avvakumov, Marek Filakovský, Jakub Opršal +2
We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H.…
cs.CG2024
Eight-Partitioning Points in 3D, and Efficiently Too
Boris Aronov, Abdul Basit, Indu Ramesh +2
An {\em eight-partition} of a finite set of points (respectively, of a continuous mass distribution) in consists of three planes that divide the space into octan…
cs.CC2023
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal +2
A linearly ordered (LO) -colouring of a hypergraph is a colouring of its vertices with colours such that each edge contains a unique maximal colour. Deciding wheth…