4 papers
Large cardinal characterizations via compactness for list colourings
Roman Feller, Peter Holy
We investigate compactness properties with respect to list colouring, a certain form of graph colouring, with infinitely many colours. We introduce a new hierarchy of compactness c…
Cut-homotopies and the complexity of edge-coloring problems
Alexey Barsukov, Roman Feller, Maximilian Hadek +1
We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We s…
Decidability of Interpretability
Roman Feller, Michael Pinsker
The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of Constraint Satisfaction Problems (CSPs) of first-order reducts of finitely…
An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
Roman Feller, Michael Pinsker
For a set F of finite tournaments, the F-free orientation problem is the problem of deciding if a given finite undirected graph can be oriented in such a way that the resulting ori…