On the complexity of the 3-kernel problem in some classes of digraphs

DOI10.7151/dmgt.1727zbMath1292.05124OpenAlexW1975584720MaRDI QIDQ2442275

César Hernández-Cruz, Pavol Hell

Publication date: 2 April 2014

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1727

zbMATH Keywords

NP-completenesskernelmultipartite tournament3-kernelcyclically 3-partite digraphsk-quasi-transitive digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

\((H, k)\)-reachability in \(H\)-arc-colored digraphs ⋮ On the existence of 3- and 4-kernels in digraphs ⋮ Some results on 4-transitive digraphs ⋮ A new generalization of kernels in digraphs ⋮ On the existence of \((k,l)\)-kernels in infinite digraphs: a survey ⋮ Domination in Digraphs ⋮ On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the existence and number of (\(k+1\))-kings in \(k\)-quasi-transitive digraphs
• \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs
• On the existence of \(k\)-kernels in digraphs and in weighted digraphs
• \(k\)-kernels in multipartite tournaments
• On the structure of strong 3-quasi-transitive digraphs
• A counterexample to a generalization of Richardson's theorem
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• Recent problems and results about kernels in directed graphs
• k-kernels in generalizations of transitive digraphs
• Cyclically k-partite digraphs and k-kernels
• Quasi‐transitive digraphs
• On weakly ordered systems

This page was built for publication: On the complexity of the 3-kernel problem in some classes of digraphs