Article in volume
Authors:
Germán Benítez-Bobadilla
Instituto de Mateáticas, Universidad Nacional Autónoma de México
email: gbenitez@matem.unam.mx
Hortensia Galeana-Sánchez
Instituto de Matemáticas, UNAMUniversidad Nacional Autónoma de MéxicoCiudad Universitaria04510, México, D.F.MEXICO
email: hgaleana@matem.unam.mx
César Hernández-Cruz
Facultad de Ciencias, Universidad Nacional Autónoma de México
email: japo@ciencias.unam.mx
Title:
Panchromatic patterns by paths
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 519-537
Received: 2021-08-28 , Revised: 2022-04-12 , Accepted: 2022-04-23 , Available online: 2022-05-18 , https://doi.org/10.7151/dmgt.2459
Abstract:
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 \rightarrow V_H$. An
$H$-path of $D$ is a path $(v_0, \dots, 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 \le i \le n-1$. For $u, v
\in 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 \subseteq 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 $\widetilde{\mathscr{B}}_1$ as the set of digraphs $H$ such that any
$H$-arc-coloured tournament has an absorbent by $H$-paths vertex; the set
$\widetilde{\mathscr{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 $\widetilde{\mathscr{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 digraphs in
$\widetilde{\mathscr{B}}_3$. In particular, we show that if a specific digraph
is not in $\widetilde{\mathscr{B}}_3$, then the structure of the digraphs in the
family is completely determined.
Keywords:
kernel of a digraph, kernel by monochromatic paths, panchromatic pattern, kernel by $H$-walks, kernel by $H$-paths
References:
- 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 - J. Bang-Jensen and G.Z. Gutin, Digraphs (Springer-Verlag, London, 2009).
- 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 - 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 - J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, London, 2008).
- 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 - 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 - 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 - 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 - 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 - P. Hell and C. Hernández-Cruz, Minimal digraph obstructions for small matrices (2016).
arXiv: 1605.09587 - V. Linek and B. Sands, A note on paths in edge-coloured tournaments, Ars Combin. 44 (1996) 225–228.
- 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
Close