Geodesic
Helly and strong Helly numbers of $B_k$-EPG and $B_k$-VPG graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1237-1252

Voir la notice de l'article provenant de la source Library of Science

EPG graphs were introduced by Golumbic, Lypshteyn, and Stern in 2009 and consist of the intersection graphs of sets of paths on the orthogonal grid, whose intersections are taken considering the edges of the paths. If the intersections of the paths consider the vertices and not the edges, the resulting graph class is called VPG graphs. A path P is a B_k-path if it contains at most k bends. B_k-EPG and B_k-VPG graphs are the intersection graphs of B_k-paths on the orthogonal grid, considering the intersection of edges and vertices, respectively. A family ℱ is h-Helly when every h-intersecting subfamily ℱ' of it satisfies core(ℱ')≠∅. If for every subfamily ℱ' of ℱ, there are h subsets whose core equals the core of ℱ', then ℱ is said to be strong h-Helly. The Helly number of the family ℱ is the least integer h, such that ℱ is h-Helly. Similarly, the strong Helly number of ℱ is the least h, for which ℱ is strong h-Helly. In this paper, we solve the problem of determining both the Helly and strong Helly numbers, for B_k-EPG, and B_k-VPG graphs, for each value k.
Keywords: EPG, VPG, path, grid, bend, Helly number, strong Helly 
@article{DMGT_2023_43_4_a19,
     author = {Bornstein, Claudson and Morgenstern, Gila and Santos, Tanilson D. and Souza, Ueverton S. and Szwarcfiter, Jayme L.},
     title = {Helly and strong {Helly} numbers of $B_k${-EPG} and $B_k${-VPG} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1237--1252},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a19/}
}
TY  - JOUR
AU  - Bornstein, Claudson
AU  - Morgenstern, Gila
AU  - Santos, Tanilson D.
AU  - Souza, Ueverton S.
AU  - Szwarcfiter, Jayme L.
TI  - Helly and strong Helly numbers of $B_k$-EPG and $B_k$-VPG graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1237
EP  - 1252
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a19/
LA  - en
ID  - DMGT_2023_43_4_a19
ER  - 
%0 Journal Article
%A Bornstein, Claudson
%A Morgenstern, Gila
%A Santos, Tanilson D.
%A Souza, Ueverton S.
%A Szwarcfiter, Jayme L.
%T Helly and strong Helly numbers of $B_k$-EPG and $B_k$-VPG graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1237-1252
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a19/
%G en
%F DMGT_2023_43_4_a19
Bornstein, Claudson; Morgenstern, Gila; Santos, Tanilson D.; Souza, Ueverton S.; Szwarcfiter, Jayme L. Helly and strong Helly numbers of $B_k$-EPG and $B_k$-VPG graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1237-1252. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a19/