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

DOI10.7151/DMGT.1727MaRDI QIDQ2442275zbMATH OpenOpenAlexFDO

Authors César Hernández-Cruz, Pavol Hell

Publication date 2 April 2014

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

3-kernelcyclically 3-partite digraphsk-quasi-transitive digraphkernelmultipartite tournamentNP-completeness

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Recommendations

• On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
• On the existence of 3- and 4-kernels in digraphs
• Strong kernel in certain oriented networks
• Acyclic kernel number of oriented cycle related graphs
• \(k\)-kernels in multipartite tournaments

Cites work

• k-kernels in k-transitive and k-quasi-transitive digraphs
• k-kernels in generalizations of transitive digraphs
• \(k\)-kernels in multipartite tournaments
• A counterexample to a generalization of Richardson's theorem
• Cyclically k-partite digraphs and k-kernels
• Graph theory
• scientific article; zbMATH DE number 3900787 (Why is no real title available?)
• scientific article; zbMATH DE number 579329 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• On the existence and number of (k+1)-kings in k-quasi-transitive digraphs
• On the existence of \(k\)-kernels in digraphs and in weighted digraphs
• On the structure of strong 3-quasi-transitive digraphs
• On weakly ordered systems
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Quasi‐transitive digraphs
• Recent problems and results about kernels in directed graphs

Cited in

(18)

• Even kernels
• Combinatorial game theory foundations applied to digraph kernels
• On the existence of 3- and 4-kernels in digraphs
• Kernels in digraphs with covering number at most 3
• On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
• On the existence of \((k,l)\)-kernels in infinite digraphs: a survey
• Quasi-transitive digraphs and their extensions
• Domination in digraphs
• scientific article; zbMATH DE number 175833 (Why is no real title available?)
• Expressive power of digraph solvability
• Some results on 4-transitive digraphs
• A new generalization of kernels in digraphs
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• \((H, k)\)-reachability in \(H\)-arc-colored digraphs
• \(k\)-kernels in multipartite tournaments
• Critical kernel imperfectness in 4-quasi-transitive digraphs and 4-anti-transitive digraphs of small diameter
• The theorem of Richardson and its generalizations: a survey
• Some new families of KP-digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2442275)