×

Richardson’s theorem in quasi-transitive and pre-transitive digraphs. (English) Zbl 1442.05075

Summary: A subset \(N\) of \(V(D)\) is said to be a kernel if it satisfies the following two properties: (1) for any two different vertices \(x\) and \(y\) in \(N\) there is no arc between them, and (2) for each vertex \(u\) in \(V(D)\setminus N\) there exists \(v\) in \(N\) such that \((u,v) \in\) A \((D)\). If every induced subdigraph of \(D\) has a kernel, \(D\) is said to be a kernel perfect digraph. In [H. Galeana-Sánchez and R. Rojas-Monroy, Discrete Math. 275, No. 1–3, 129–136 (2004; Zbl 1036.05026)] and [H. Galeana-Sánchez and R. Rojas-Monroy, ibid. 306, No. 16, 1969–1974 (2006; Zbl 1100.05042)] the authors establish sufficient conditions to guarantee the kernel perfectness in digraphs, possibly infinite, where their set of arcs can be partitioned into at most two pre-transitive (resp. quasi-transitive) digraphs. In the present paper we consider those, also possibly infinite, digraphs where the set of arcs can be partitioned into at least three quasi-transitive (resp. pre-transitive) digraphs, and establish sufficient conditions to guarantee the kernel perfectness. In both cases we derive Richardson’s theorem, which states that every finite digraph without cycles of odd length has a kernel.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2000), London: Springer, London
[2] Berge, C., Nouvelles extensions du noyau d’un graphe et ses applications en théorie des jeux, Publ. Econom., 6, 6-11 (1977)
[3] Berge, C., Graphs (1989), Amsterdam: North-Holland, Amsterdam
[4] Chvátal, V.: On the computational complexity of finding a kernel, Report CRM300, Centre de Recherches Mathématiques, Université de Montréal (1973)
[5] Duchet, P., Graphes noyau-parfaits, Ann. Discrete Math., 9, 93-101 (1980) · Zbl 0462.05033
[6] Fraenkel, AS, Planar Kernel and Grundy with d \(\le 3, d_{out}\le 2, d_{in}\le 2\), are NP-complete, Discrete Appl. Math., 3, 257-262 (1981) · Zbl 0493.68040
[7] Fraenkel, A.S.: Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction. Electron J. Combin. 14 (DS2) (2009). http://www.combinatorics.org/ojs/index.php/eljc/article/view/ds2/pdf · Zbl 0871.90147
[8] Galeana-Sánchez, H.; Rojas-Monroy, R., Kernels in quasi-transitive digraphs, Discrete Math., 306, 1969-1974 (2006) · Zbl 1100.05042
[9] Galeana-Sánchez, H.; Rojas-Monroy, R., Kernels in pretransitive digraphs, Discrete Math., 275, 129-136 (2004) · Zbl 1036.05026
[10] Ghouilá-Houri, A., Caractérisation des graphes non orientés dont on peut orienter les arretes de maniere obtenir le graphe d un relation d ordre, C.R. Acad. Sci. Paris, 254, 1370-1371 (1962) · Zbl 0105.35503
[11] Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton: Princeton University Press, Princeton · Zbl 0063.05930
[12] Richardson, M., Solutions of irreflexive relations, Ann. Math., 58, 2, 573 (1953) · Zbl 0053.02902
[13] Sánchez-López, R., Infinite kernel perfect digraphs, AKCE Int., 14, 165-171 (2017) · Zbl 1372.05091
[14] Sands, B.; Sauer, N.; Woodrow, R., On monochromatic paths in edge coloured digraphs, J. Combin. Theory Ser. B, 33, 271-275 (1982) · Zbl 0488.05036
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.