78 citations · 133 across the 7 of their papers we have counts for
6 papers · 1 filter
A topological proof of the Hell-Nešetřil dichotomy
Sebastian Meyer, Jakub Opršal
We provide a new proof of a theorem of Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990] using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theor…
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…
An invitation to the promise constraint satisfaction problem
Andrei Krokhin, Jakub Opršal
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. Afte…
Topology and adjunction in promise constraint satisfaction
Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a -colouring of a graph that is promised to be -colourable, where $c\g…
The complexity of 3-colouring -colourable graphs
Andrei Krokhin, Jakub Opršal
We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph , the -colouring problem is to decide whether a given gra…
Algebraic approach to promise constraint satisfaction
Libor Barto, Jakub Bulín, Andrei Krokhin +1
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) h…