Independent and monochromatic absorbent sets in infinite digraphs
Alejandro Contreras-Balbuena, Hortensia Galeana‐Sánchez, Rocı́o Rojas-Monroy · AKCE International Journal of Graphs and Combinatorics · 2015
Let be a digraph, we say that it is an -coloured digraph if the arcs of are coloured with at most -colours. An arc is symmetrical if is also an arc of . A directed path (resp. directed cycle) is monochromatic if all of its arcs are coloured with the same colour, and it is quasi-monochromatic if at most one of its arcs is coloured with different colour.A set is an -kernel if it satisfies the following conditions: (1) For every pair of vertices , there is no arc between them, we say that is independent.(2) For every , there exists an -monochromatic path for some , it means is absorbent by monochromatic paths. An infinite sequence of different vertices such that for every will be called an infinite outward path.In this paper we introduce the definitions of -kernel and -semikernel, but also we prove the following theorem: Let be a possibly infinite digraph, if every directed cycle and every infinite outward path has two consecutive vertices, say and , such that there exists an -monochromatic path, then has an -kernel.