Panchromatic patterns by paths

Benítez-Bobadilla, Germán ; Galeana-Sánchez, Hortensia ; Hernández-Cruz, César 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 519-537

Résumé

Let H=(V_H,A_H) be a digraph, possibly with loops, and let D=(V_D, A_D) be a loopless multidigraph with a colouring of its arcs c: A_D → V_H. An H-path of D is a path (v_0, . . . , v_n) of D such that (c(v_i-1, v_i), c(v_i,v_i+1)) is an arc of H for every 1 ≤ i ≤ n-1. For u, v ∈ V_D, we say that u reaches v by H-paths if there exists an H-path from u to v in D. A subset S ⊆ V_D is absorbent by H-paths of D if every vertex in V_D-S reaches some vertex in S by H-paths, and it is independent by H-paths if no vertex in S can reach another (different) vertex in S by H-paths. A kernel by H-paths is a subset of V_D which is independent by H-paths and absorbent by H-paths. We define ℬ̃_1 as the set of digraphs H such that any H-arc-coloured tournament has an absorbent by H-paths vertex; the set ℬ̃_2 consists of the digraphs H such that any H-arc-coloured digraph D has an independent, absorbent by H-paths set; analogously, the set ℬ̃_3 is the set of digraphs H such that every H-arc-coloured digraph D contains a kernel by H-paths. In this work, we point out similarities and differences between reachability by H-walks and reachability by H-paths. We present a characterization of the patterns H such that for every digraph D and every H-arc-colouring of D, every H-walk between two vertices in D contains an H-path with the same endpoints. We provide advances towards a characterization of the digraphs in ℬ̃_3. In particular, we show that if a specific digraph is not in ℬ̃_3, then the structure of the digraphs in the family is completely determined.

Détail

Keywords: kernel of a digraph, kernel by monochromatic paths, panchromatic pattern, kernel by $H$-walks, kernel by $H$-paths