On a class of kernel-perfect and kernel-perfect-critical graphs
Let \(G=(V,E)\) be a directed graph. Then a set \(K\) of its vertices is called a kernel if \(K\) is an independent set, and \(K\cap \Gamma^{- 1}(K)=\varnothing\), \(K\cup\Gamma^{-1}(K)=V\), where \(\Gamma^{-1}(K)\) is the set of all the vertices \(x\) of \(G\) such that there exists \(y\in K\) with \((x,y)\) being an arc of \(G\). \(G\) is called a kernel-perfect graph if all induced subgraphs of \(G\), including \(G\), have a kernel, and it is called a kernel-perfect-critical graph if \(G\) does not have a kernel but every proper induced subgraph has. In the paper a new construction of both kernel-perfect graphs and kernel-perfect-critical graphs is presented.
- On kernel-perfect critical digraphs
- New extensions of kernel perfect digraphs to kernel imperfect critical digraphs
- Recent problems and results about kernels in directed graphs
- A new method to extend kernel-perfect graphs to kernel-perfect critical graphs
- Kernel perfect and critical kernel imperfect digraphs structure
- On kernel-perfect critical digraphs
- A combinatorial theorem on ordered circular sequences of \(n_1\) \(u\)'s and \(n_2\) \(v\)'s with application to kernel-perfect graphs
- Perfect graphs, kernels, and cores of cooperative games
- Recent problems and results about kernels in directed graphs
- New classes of critical kernel-imperfect digraphs
- scientific article; zbMATH DE number 915661 (Why is no real title available?)
This page was built for publication: On a class of kernel-perfect and kernel-perfect-critical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685562)
