On kernel-perfect critical digraphs
From MaRDI portal
Let G be a digraph. An independent set N of vertices of G is called a kernel if for every vertex z of G, \(z\not\in N\), there exists a vertex \(v\in N\) such that (z,v) is an edge of G. A digraph is said to be kernel- perfect (KP) if each of its proper induced subdigraphs has a kernel. A KP digraph which has no kernel is called KP-critical. In the paper some properties of KP-critical digraphs are studied and a construction of such digraphs is given. In a addition, the sufficient conditions for a digraph to be KP are investigated.
Recommendations
- Extending kernel perfect digraphs to kernel perfect critical digraphs
- Semikernels modulo F in digraphs
- Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs
- Kernel perfect and critical kernel imperfect digraphs structure
- On a class of kernel-perfect and kernel-perfect-critical graphs
Cites work
- A counterexample to a conjecture of Meyniel on kernel-perfect graphs
- A note on kernel-critical graphs
- Extending kernel perfect digraphs to kernel perfect critical digraphs
- Extension Theorems for Solutions of Irreflexive Relations
- Graphes Noyau-Parfaits
- scientific article; zbMATH DE number 3687449 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3226832 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- On kernels and semikernels of digraphs
- On weakly ordered systems
- Solutions of irreflexive relations
- The dichromatic number of a digraph
Cited in
(38)- A new method to extend kernel-perfect graphs to kernel-perfect critical graphs
- A counterexample to a conjecture of Meyniel on kernel-perfect graphs
- Extending kernel perfect digraphs to kernel perfect critical digraphs
- On the existence of kernels and h-kernels in directed graphs
- Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
- New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
- A circular graph---counterexample to the Duchet kernel conjecture
- Kernels in a special class of digraphs
- Alternating kernels
- A combinatorial theorem on ordered circular sequences of \(n_1\) \(u\)'s and \(n_2\) \(v\)'s with application to kernel-perfect graphs
- Independent sets which meet all longest paths
- On monochromatic paths and monochromatic cycles in edge coloured tournaments
- Critical kernel imperfect problem in generalizations of bipartite tournaments
- Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks
- \(H\)-paths and \(H\)-cycles in \(H\)-coloured digraphs
- Infinite kernel perfect digraphs
- Unions of digraphs which become kernel perfect
- Independent sets and non-augmentable paths in generalizations of tournaments
- Perfect graphs, kernels, and cores of cooperative games
- Kernels and perfectness in arc-local tournament digraphs
- A sufficient condition for kernel perfectness of a digraph in terms of semikernels modulo F
- Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs
- Cycles and transitivity by monochromatic paths in arc-coloured digraphs
- A characterization of locally semicomplete CKI-digraphs
- Monochromatic kernel-perfectness of special classes of digraphs
- Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3
- New classes of critical kernel-imperfect digraphs
- A new characterization of perfect graphs
- Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments
- scientific article; zbMATH DE number 1444491 (Why is no real title available?)
- CKI-digraphs, generalized sums and partitions of digraphs
- On the kernel and related problems in interval digraphs
- On a class of kernel-perfect and kernel-perfect-critical graphs
- Critical kernel imperfectness in 4-quasi-transitive digraphs and 4-anti-transitive digraphs of small diameter
- Some new families of KP-digraphs
- Orientations of graphs in kernel theory
- \(\Gamma\)-cycles in arc-colored digraphs
- Kernels and some operations in edge-coloured digraphs
This page was built for publication: On kernel-perfect critical digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1076036)
