zbMATH — the first resource for mathematics

On the dichromatic number in kernel theory. (English) Zbl 0937.05048
Given a digraph \(D\), a subset \(N\) of its vertex set \(V(D)\) is called a kernel of \(D\) if it is independent (there is no arc joining two vertices of \(N\)) and absorbing (for each \(x\notin N\) there is an arc \(xy\) with \(y\in N\)). If every induced subdigraph of \(D\) has a kernel, then \(D\) is said to be kernel-perfect. The dichromatic number of \(D\) is the minimum number of acyclic classes into which \(V(D)\) can be partitioned. The authors give constructions of kernel-perfect digraphs with a prescribed dichromatic number and without semicycles of lengths 2 or 3. Strengthening their previous results in [Discrete Math. 94, No. 3, 181-187 (1991; Zbl 0748.05060)] they provide also results and conjectures concerning critical kernel-imperfect digraphs.

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
Full Text: EuDML
[1] BERGE C.: Graphs. North-Holland, Amsterdam, 1985. · Zbl 0566.05001
[2] GALEANA-SÁNCHEZ H.-NEUMANN-LARA V.: On kernel-perfect critical digraphs. Discrete Math. 59 (1986), 257-265. · Zbl 0593.05034
[3] GALEANA-SÁNCHEZ H.-NEUMANN-LARA V.: Extending kernel-perfect digraphs. Discrete Math. 94 (1991), 181-187. · Zbl 0748.05060
[4] GALEANA-SÁNCHEZ H.-NEUMANN-LARA V.: New extensions of kernel-perfect digraphs to critical kernel-imperfect digraphs. Graphs Combin. 10 (1994), 329-336. · Zbl 0811.05027
[5] JACOB H.-MEYNIEL H.: Extensions of Turan’s and Brook’s theorems and new notions of stability and colouring in digraphs. Ann. Discrete Math. 17, North-Holland, Amsterdam, 1983, pp. 365-370. · Zbl 0525.05027
[6] NEUMANN-LARA V.: The dichromatic number of a digraph. J. Combin. Theory Ser. B 33 (1982), 265-270. · Zbl 0506.05031
[7] Von NEUMANN J.-MORGENSTERN O.: Theory of Games and Economic Behavior. Princeton Univ. Press, Princeton, 1953. · Zbl 0053.09303
[8] RICHARDSON M.: On weakly ordered systems. Bull. Amer. Math. Soc. (2) 52 (1946), 113-116. · Zbl 0060.06506
[9] RICHARDSON M.: Solutions of irreflexive relations. Ann. of Math. (2) 58 (1953), 573-590. · Zbl 0053.02903
[10] RICHARDSON M.: Extension theorems for solutions of irreflexive relations. Proc. Math. Acad. Sci. U. S. A. 39 (1953), 649-655. · Zbl 0053.02903
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.