On panchromatic patterns

Since the classic book of Berge (1985) it is well known that every digraph contains a kernel by paths. This was generalised by Sands et al. (1982) who proved that every edge two-coloured digraph has a kernel by monochromatic paths. More generally, given DD and HH two digraphs, DD is HH-coloured iff the arcs of DD are coloured with the vertices of HH. Furthermore, an HH-walk in DD is a sequence of arcs forming a walk in DD whose colours are a walk in HH. With this notion of HH-walks, we can define HH-independence, which is the absence of such a walk pairwise, and HH-absorbance, which is the existence of such a walk towards the absorbent set. Thus, an HH-kernel is a subset of vertices which is both HH-independent and HH-absorbent. The aim of this paper is to characterise those HH, which we call panchromatic patterns  , for which all DD and all HH-colourings of DD admits an HH-kernel. This solves a problem of Arpin and Linek from 2007 (Arpin and Linek, 2007).