×

zbMATH — the first resource for mathematics

Extending kernel perfect digraphs to kernel perfect critical digraphs. (English) Zbl 0748.05060
An independent subset \(K\) of the vertex set of a digraph \(D\) is said to be a kernel of \(D\) if every vertex which does not belong to \(K\) has a successor in \(K\).
The authors have proved that any kernel perfect digraph (every induced subdigraph has a kernel) can be extended to a kernel perefect critical digraph (with no kernels, but the deletion of any vertex produces a digraph with a kernel).

MSC:
05C20 Directed graphs (digraphs), tournaments
Keywords:
digraph; kernel
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berge, C., Graphs, (1985), North-Holland Amsterdam · Zbl 0334.05117
[2] Duchet, P., Representation; noyaux en théorie des graphes et hypergraphes, (1979), Thése Paris
[3] Duchet, P., Graphes noyau-parfaits, (), 93-101 · Zbl 0462.05033
[4] Duchet, P.; Meyniel, H., A note on kernel critical graphs, Discrete math., 33, 103-105, (1981) · Zbl 0456.05032
[5] Erdős, P., Problems and results in number theory and graph theory, Proc. 9th manitoba conf. on numerical mathematics and computing, 3-21, (1979)
[6] Galeana-Sánchez, H., A counterexample to a conjecture of meyniel on kernel perfect graphs, Discrete math., 41, 105-107, (1982) · Zbl 0484.05035
[7] Galeana-Sánchez, H.; Neumann-Lara, V., On kernels and semikernels of digraphs, Discrete math., 48, 67-76, (1984) · Zbl 0529.05024
[8] Galeana-Sánchez, H.; Neumann-Lara, V., On kernel-perfect critical digraphs, Discrete math., 59, 257-265, (1986) · Zbl 0593.05034
[9] Jacon, H., Etude théorique du noyau d’ un graphe, ()
[10] H. Meyniel, Extension du nombre chromatique et du nombre de stabilite, preprint.
[11] Neumann-Lara, V., Seminucleos de una digrafica, An inst. mat. univ. nac. autónoma México, II, (1971)
[12] Neumann-Lara, V., The dichromatic number of a digraph, J. combin. theory ser. B, 33, 265-270, (1982) · Zbl 0506.05031
[13] Richardson, M., On weakly ordered systems, Bull. amer. math. soc., 52, 113, (1946) · Zbl 0060.06506
[14] Richardson, M., Solutions of irreflexive relations, Ann. math., 58, 2, 573, (1953) · Zbl 0053.02902
[15] Richardson, M., Extension theorems for solutions of irreflexive relations, Proc. nat. acad. sci. USA, 39, 649, (1953) · Zbl 0053.02903
[16] J.^Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior (Princeton Univ. Press., Princeton). · Zbl 0063.05930
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.