Kernels in digraphs with colored vertices

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Review text

The paper introduces the notion of an up-color kernel for vertex-colored digraphs, extending the classical concept of a kernel by incorporating a color hierarchy. The paper gives a precise definition in which every vertex outside the kernel must be absorbed by an adjacent kernel vertex of strictly larger color, while the kernel remains independent and contains no vertex of color zero.\N\NThe main contribution is the derivation of necessary and sufficient conditions for the existence of up-color kernels for several classes of digraphs. In particular, the authors characterize this property for directed paths, even cycles, forests, wheels, unicyclic digraphs, and directed cycles with chords.\N\NA further significant contribution is the investigation of up-color kernels under standard digraph operations. The paper considers Cartesian and strong products, Zykov sums, generalized in-crowns and ex-crowns, and line digraphs, obtaining structural and coloring conditions that determine when the resulting digraph possesses an up-color kernel.\N\NThe treatment of line digraphs is particularly noteworthy. The paper introduces outer and inner colorings of the line digraph and establishes, under an explicit coloring condition, equality between the number of up-color kernels of a digraph and those of its outer-colored line digraph. The examples also demonstrate the necessity of the stated hypothesis and the different behavior of the inner coloring.\N\NThe paper concludes by identifying several natural problems concerning characterization of colorings, enumeration of up-color kernels, algorithmic questions, and extensions to semi-kernels and \((k,l)\)-kernels.

Cites work

This page was built for publication: Kernels in digraphs with colored vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7299952)