Tue, 18 Feb 2025, 1:25 pm MT
Conservative graph-colouring problems, also known as list homomorphism problems, have been examined for various classes of finite digraphs. Each instance consists of a finite digraph along with a list of permitted values for each vertex. Lifting the scenario to infinite digraphs G, the 1-orbits of an oligomorphic subgroup Ω of Aut(G) take the role of elements. A conservative template in this framework is enriched by a unary relation for all unions of 1-orbits of Ω. Assuming only access to unions of pairs of 1-orbits, we obtain the first structural dichotomy for ω-categorical smooth digraphs of algebraic length 1, yielding a hardness criterion for the respective conservative graph-colouring problems. We thereby overcome previous obstacles to lifting structural results for digraphs in this context from finite to ω-categorical structures -- the strongest lifting results hitherto applying only to undirected graphs.
This is joint work with Marcin Kozik, Tomáš Nagy, and Michael Pinsker.