MeikeHatzel

We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, …

Motivated by colouring minimal Cayley graphs, in 1978 Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large …