On Panchromatic Digraphs and the Panchromatic Number.

Let D = ( V, A) be a simple finite digraph, and let $${\pi(D)}$$ , the panchromatic number of D, be the maximum number of colours k such that for each (effective, or onto) colouring of its arcs $${\varsigma : A \to [k]}$$ a monochromatic path kernel N ⊂ V, as introduced in Galeana-Sánchez (Discrete Math 184: 87-99, ), exists. It is not hard to see that D has a kernel-in the sense of Von Neumann and Morgenstern (Theory of games and economic behaviour. Princeton University Press, Princeton, )-if and only if $${\pi(D) = |A|}$$ . In this note this invariant is introduced and some of its structural bounds are studied. For example, the celebrated theorem of Sands et al. (J Comb Theory Ser 33: 271-275, ), in terms of this invariant, settles that $${\pi(D) \geq 2}$$ . It will be proved that where $${\chi(\cdot)}$$ denotes the chromatic number, $${L(\cdot)}$$ denotes the line digraph, $${\theta(\cdot)}$$ denotes the minimum partition into complete graphs of the underlying graph and $${\text{d}_c(\cdot)}$$ denotes the dichromatic number. We also introduce the notion of a panchromatic digraph which is a digraph D such that for every k ≤ | A| and every k-colouring of its arcs, it has a monochromatic path kernel. Some classes of panchromatic digraphs are further characterised. [ABSTRACT FROM AUTHOR]