Pseudo-loops and infinite directed graph-colouring

Johanna Brunar ( Vienna University of Technology )

In the early stages of the systematic research programme on Constraint Satisfaction Problems (CSPs), those induced by finite graphs were among the first to be studied. Hell and Nešetřil showed already in 1990 that every finite undirected non-bipartite graph either gives rise to an NP-complete CSP, or has a loop (in which case its CSP trivial). This result was later extended to finite directed graphs. When it comes to infinity, the graphs ’closest to finite’ are the ones whose factor by their automorphism group is finite. While the Hell-Nešetřil theorem for undirected graphs has been successfully generalised to this framework, the directed case poses significant challenges. For the first time, we overcome previous obstacles to lifting results for digraphs from the finite to the infinite realm.

Based on joint work with Marcin Kozik, Tomáš Nagy, Michael Pinsker, and Moritz Schöbi.