On Panchromatic Digraphs and the Panchromatic Number

• Published in: Graphs and combinatorics 2015-01, Vol.31 (1), p.115-125
• Main Authors: Galeana, Hortensia, Strausz, Ricardo
• Format: Article
• Language: English
• Subjects: Color; Colour; Combinatorial analysis; Combinatorics; Engineering Design; Graph theory; Graphs; Invariants; Kernels; Mathematics; Mathematics and Statistics; Original Paper; Texts
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-013-1367-z

Let D =  ( V , A ) be a simple finite digraph, and let π ( D ) , the panchromatic number of D , be the maximum number of colours k such that for each (effective, or onto) colouring of its arcs ς : A → [ 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 π ( 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 π ( D ) ≥ 2 . It will be proved that π ( D ) < | A | ⟺ π ( D ) < min 2 χ ( D ) , χ ( L ( D ) ) , θ ( D ) + max d c ( K i ) + 1 , where χ ( · ) denotes the chromatic number, L ( · ) denotes the line digraph, θ ( · ) denotes the minimum partition into complete graphs of the underlying graph and d c ( · ) 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.