A dichotomy for the kernel by H‐walks problem in digraphs
Hortensia Galeana‐Sánchez, César Hernández‐Cruz · Journal of Graph Theory · 2018
Abstract Let be a digraph which may contain loops, and let be a loopless digraph with a coloring of its arcs . An ‐walk of is a walk of such that is an arc of , for every . For , we say that reaches by ‐walks if there exists an ‐walk from to in . A subset is a kernel by ‐walks of if every vertex in reaches by ‐walks some vertex in , and no vertex in can reach another vertex in by ‐walks. A panchromatic pattern is a digraph such that every ‐arc‐colored digraph has a kernel by ‐walks. In this study, we prove that every digraph is either a panchromatic pattern, or the problem of determining whether an arc‐colored digraph has a kernel by ‐walks is ‐complete.