Richardson's theorem
From Egres Open
Theorem[1]. Every digraph without an odd directed cycle is kernel-perfect.
This theorem has several generalizations:
- If every odd directed cycle in a digraph D has at least two symmetric arcs (the reversed arcs are also in D), then D is kernel-perfect [2].
- If every odd directed cycle in a digraph D has two pseudodiagonals of the form [math](x_i, x_{i+2})[/math] and [math](x_{i+1}, x_{i+3})[/math] then D is kernel-perfect [3].
Related results on the structure of kernel-perfect and critical kernel-imperfect graphs are described by Galeana-Sánchez and Guevara [4].
References
- ↑ M. Richardson, On weakly ordered systems, Bull. Amer. Math. Soc. 52 (1946), 113-116. Project Euclid link
- ↑ P. Duchet, Representation; noyaux en theorie des graphes et hypergraphes, Thèse, Paris (1979)
- ↑ P. Duchet, H. Meyniel, Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientés, Discrete Math. 43 (1983), 21–27, DOI link, ResearchGate link
- ↑ H. Galeana-Sánchez, M. Guevara, Kernel perfect and critical kernel imperfect digraphs structure, Electronic Notes in Discrete Mathematics 28 (2007), 401-408, DOI link. Proceedings version
