On the dichromatic number in kernel theory
Hortensia Galeana‐Sánchez, V. Neumann‐Lara · Czech digital mathematics library · 1998
The dichromatic number of a digraph D is the minimum cardinal of a partition of V(D) into acyclic classes.The dichromatic number gives a measure of the complexity of the cyclic structure of D.A kernel N of a digraph D is an independent set of vertices such that for each z € V(D) -N there exists a zN-arc in D. When every induced subdigraph of D has a kernel, the digraph D is said to be kernel-perfect.We say that D is a critical kernel-imperfect digraph if D does not have a kernel but every proper induced subdigraph of D does have at least one.In this paper we prove the existence of kernel-perfect digraphs with arbitrarily large dichromatic number whose underlying graph has no triangles and we prove the existence of critical kernel-imperfect digraphs with arbitrarily large dichromatic number and without directed cycles of length two or three.The earliest sufficient conditions for the existence of kernels in digraphs include only digraphs with dichromatic number at most two.Finally we state some open problems relating the dichromatic number and the kernel of a digraph.