Showing cs.CCShow all
2 papers · 1 filter
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.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…