New classes of panchromatic digraphs
Hortensia Galeana‐Sánchez, Micael Toledo · AKCE International Journal of Graphs and Combinatorics · 2015
A digraph with a -colouring of its arcs is said to have a -kernel if there exists a subset of such that there are no monochromatic -paths for any two vertices , but for every , there exists a vertex such that there is a monochromatic -path in . The panchromatic number, , of is the greatest integer for which has a -kernel for every possible -colouring of its arcs. is said to be a panchromatic digraph if, for every and every -colouring , has a -kernel. In this paper we study the panchromaticity of cycles. In particular, we show that even cycles are panchromatic and that when is an odd cycle. We also set sufficient conditions, in terms of its induced subdigraphs, for a digraph to be panchromatic, and we show through counterexamples that these results cannot be improved.