1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Panchromatic Patterns By Paths

Published Online: 27 May 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 28 Aug 2021
Accepted: 23 Apr 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let H = (VH, AH) be a digraph, possibly with loops, and let D = (VD, AD) be a loopless multidigraph with a colouring of its arcs c : ADVH. An H-path of D is a path (v0, . . ., vn) of D such that (c(vi−1, vi), c(vi, vi+1)) is an arc of H for every 1 ≤ in − 1. For u, vVD, we say that u reaches v by H-paths if there exists an H-path from u to v in D. A subset SVD is absorbent by H-paths of D if every vertex in VDS 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 VD which is independent by H-paths and absorbent by H-paths.

We define ˜1 {\widetilde {\cal B}_1} as the set of digraphs H such that any H-arc-coloured tournament has an absorbent by H-paths vertex; the set ˜2 {\widetilde {\cal B}_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 {\widetilde {\cal B}_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 di-graphs in ˜3 {\widetilde {\cal B}_3} . In particular, we show that if a specific digraph is not in ˜3 {\widetilde {\cal B}_3} , then the structure of the digraphs in the family is completely determined.

Keywords

MSC 2010

[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.04210.1016/j.disc.2006.09.042 Search in Google Scholar

[2] J. Bang-Jensen and G.Z. Gutin, Digraphs (Springer-Verlag, London, 2009).10.1007/978-1-84800-998-1 Search in Google Scholar

[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.01310.1016/j.disc.2018.09.013 Search in Google Scholar

[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.02010.1016/j.dam.2019.04.020 Search in Google Scholar

[5] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, London, 2008).10.1007/978-1-84628-970-5 Search in Google Scholar

[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.00510.1016/j.jctb.2018.11.005 Search in Google Scholar

[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.01310.1016/j.dam.2017.10.013 Search in Google Scholar

[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.2238910.1002/jgt.22389 Search in Google Scholar

[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.01410.1016/j.disc.2016.03.014 Search in Google Scholar

[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.02410.1016/j.disc.2003.10.024 Search in Google Scholar

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

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

[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-810.1016/0095-8956(82)90047-8 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo