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

Bibliographie

[1] P. Arpin and V. Linek, Reachability problems in edge-colored digraphs, Discrete Math. 307 (2007) 2276–2289. https://doi.org/10.1016/j.disc.2006.09.042

[2] J. Bang-Jensen and G.Z. Gutin, Digraphs (Springer-Verlag, London, 2009).

[3] L. Beaudou, L. Devroye and G. Hahn, A lower bound on the size of an absorbing set in an arc-coloured tournament, Discrete Math. 342 (2019) 143–144. https://doi.org/10.1016/j.disc.2018.09.013

[4] G. Benítez-Bobadilla, H. Galeana-Sánchez and C. Hernández-Cruz, Characterization of color patterns by dynamic H-paths, Discrete Appl. Math. 267 (2019) 41–51. https://doi.org/10.1016/j.dam.2019.04.020

[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, London, 2008).

[6] N. Bousquet, W. Lochet and S. Thomassé, A proof of the Erdős-Sands-Sauer-Woodrow conjecture, J. Combin. Theory Ser. B 137 (2019) 316–319. https://doi.org/10.1016/j.jctb.2018.11.005

[7] P. Delgado-Escalante, H. Galeana-Sánchez and E. O'Reilly-Regueiro, Alternating kernels, Discrete Appl. Math. 236 (2018) 153–164. https://doi.org/10.1016/j.dam.2017.10.013

[8] H. Galeana-Sánchez and C. Hernández-Cruz, A dichotomy for the kernel by H-walks problem in digraphs, J. Graph Theory 90 (2019) 213–226. https://doi.org/10.1002/jgt.22389

[9] H. Galeana-Sánchez and R. Strausz, On panchromatic patterns, Discrete Math. 339 (2016) 2536–2542. https://doi.org/10.1016/j.disc.2016.03.014

[10] G. Hahn, P. Ille and R.E. Woodrow, Absorbing sets in arc-coloured tournaments, Discrete Math. 283 (2004) 93–99. https://doi.org/10.1016/j.disc.2003.10.024

[11] P. Hell and C. Hernández-Cruz, Minimal digraph obstructions for small matrices (2016). arXiv: 1605.09587

[12] V. Linek and B. Sands, A note on paths in edge-coloured tournaments, Ars Combin. 44 (1996) 225–228.

[13] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory Ser. B 33 (1982) 271–275. https://doi.org/10.1016/0095-8956(82)90047-8