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, 1998), 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, 1944)—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, 1982), in terms of this invariant, settles that $${\pi(D) \geq 2}$$ . It will be proved that $$\pi(D) < |A| \iff \pi(D) < \min \left\{2\sqrt{\chi(D)}, \chi(L(D)), \theta(D) + \max {\text d}_c(K_i) + 1\right\},$$ 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.