On the complexity of the 3-kernel problem in some classes of digraphs
Pavol Hell, César Hernández‐Cruz · Discussiones Mathematicae Graph Theory · 2013
Let D be a digraph with the vertex set V (D) and the arc setIt is known that the problem of determining whether a digraph has a kernel ("the kernel problem") is NP-complete, even in quite restricted families of digraphs.In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs.As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.