2016/05/31 by Hortensia Galeana-Sánchez, Galeana-Sánchez, Hortensia, César Hernández-Cruz +1
Mathematics · #05C20 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20
paper · pdf · doi:10.48550/arxiv.1605.09589
20 pages, 3 figures
arxiv created 2016/05/31 · arxiv updated 2016/06/01
Let H = (VH, AH) be a digraph which may contain loops, and let D = (VD, AD) be a loopless digraph with a coloring of its arcs c: AD → VH. An H-walk of D is a walk (v0, …, vn) of D such that (c(vi-1, vi), c(vi, vi+1)) is an arc of H, for every 1 ≤ i ≤ n-1. For u, v ∈ VD, we say that u reaches v by H-walks if there exists an H-walk from u to v in D. A subset S ⊆ VD is a kernel by H-walks of D if every vertex in VD ∖ S reaches by H-walks some vertex in S, and no vertex in S can reach another vertex in S by H-walks. A panchromatic pattern is a digraph H such that every arc-colored digraph D has a kernel by H-walks. In this work, we prove that every digraph H is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph D has a kernel by H-walks is NP-complete.