Search

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 Bk-path if it contains at most k bends. Bk-EPG and Bk-VPG graphs are the intersection graphs of Bk-paths on the orthogonal grid, considering the intersection of edges and vertices, respectively. A family F is h-Helly when every h-intersecting sub-family F' of it satisfies core(F') ≠ 0. If for every subfamily F' of F, there are h subsets whose core equals the core of F', then F is said to be strong h-Helly. The Helly number of the family F is the least integer h, such that F is h-Helly. Similarly, the strong Helly number of F is the least h, for which F is strong h-Helly. In this paper, we solve the problem of determining both the Helly and strong Helly numbers, for Bk-EPG, and Bk-VPG graphs, for each value k. [ABSTRACT FROM AUTHOR]

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph G is a graph that admits a representation where its vertices correspond to paths in a grid Q, such that two vertices of G are adjacent if and only if their corresponding paths in Q have a common edge. If the paths in the representation have at most k bends, we say that it is a Bk-EPG representation. A collection C of sets satisfies the Helly property when every sub-collection of C that is pairwise intersecting has at least one common element. In this paper, we show that given a graph G and an integer k, the problem of determining whether G admits a Bk-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-Bk-EPG representation, is in NP, for every k bounded by a polynomial function of jV (G)j. Moreover, we show that the problem of recognizing Helly-B1-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs. [ABSTRACT FROM AUTHOR]

A graph G has p -intersection number at most d if it is possible to assign to every vertex u of G , a subset S ( u ) of some ground set U with | U | = d in such a way that distinct vertices u and v of G are adjacent in G if and only if | S ( u ) ∩ S ( v ) | ≥ p . We show that every minimal forbidden induced subgraph for the hereditary class G ( d , p ) of graphs whose p -intersection number is at most d , has order at most ( 2 d + 1 ) 2 , and that the exponential dependence on d in this upper bound is necessary. For p ∈ { d − 1 , d − 2 } , we provide more explicit results characterizing the graphs in G ( d , p ) without isolated/universal vertices using forbidden induced subgraphs. [ABSTRACT FROM AUTHOR]