BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

María Pía Mazzoleni

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.CODiscrete MathematicsData Structures and Algorithms

Catalog footprint

Research overview

5works
3topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

5 publications

preprint2022arXiv

Edge Intersection Graphs of Paths on a Triangular Grid

We introduce a new class of intersection graphs, the edge intersection graphs of paths on a triangular grid, called EPGt graphs. We show similarities and differences from this new class to the well-known class of EPG graphs. A turn of a path at a grid point is called a bend. An EPGt representation in which every path has at most kk bends is called a Bk_k-EPGt representation and the corresponding graphs are called Bk_k-EPGt graphs. We provide examples of B2_{2}-EPG graphs that are B1_{1}-EPGt. We characterize the representation of cliques with three vertices and chordless 4-cycles in B1_{1}-EPGt representations. We also prove that B1_{1}-EPGt graphs have Strong Helly number 33. Furthermore, we prove that B1_{1}-EPGt graphs are 77-clique colorable.

Open access
preprint2020arXiv

On B1B_1-EPG and EPT graphs

This research contains as a main result the prove that every Chordal B1B_1-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B1B_1-EPG graph which does not admit a Helly-B1B_1-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-B1B_1 EPG, namely Bipartite, Block, Cactus and Line of Bipartite graphs.

Open access
preprint2016arXiv

Helly EPT\mathbf{EPT} graphs on bounded degree trees: forbidden induced subgraphs and efficient recognition

The edge intersection graph of a family of paths in host tree is called an EPTEPT graph. When the host tree has maximum degree hh, we say that GG belongs to the class [h,2,2][h,2,2]. If, in addition, the family of paths satisfies the Helly property, then G∈G \in Helly [h,2,2][h,2,2]. The time complexity of the recognition of the classes [h,2,2][h,2,2] inside the class EPTEPT is open for every h>4h> 4. Golumbic et al. wonder if the only obstructions for an EPTEPT graph belonging to [h,2,2][h,2,2] are the chordless cycles CnC_n for n>hn> h. In the present paper, we give a negative answer to that question, we present a family of EPTEPT graphs which are forbidden induced subgraphs for the classes [h,2,2][h,2,2]. Using them we obtain a total characterization by induced forbidden subgraphs of the classes Helly [h,2,2][h,2,2] for h≥4h\geq 4 inside the class EPTEPT. As a byproduct, we prove that Helly EPTEPT∩[h,2,2]=\cap [h,2,2]= Helly [h,2,2][h,2,2]. We characterize Helly [h,2,2][h,2,2] graphs by their atoms in the decomposition by clique separators. We give an efficient algorithm to recognize Helly [h,2,2][h,2,2] graphs.

Open access
preprint2013arXiv

Characterizing [h,2,1] graphs by minimal forbidden induced subgraphs

An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. The class of graphs which admit a VPT representation in a host tree with maximum degree at most h is denoted by [h,2,1]. The classes [h,2,1] are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. In this paper we associate the minimal forbidden induced subgraphs for [h,2,1] which are VPT with (color) h-critical graphs. We describe how to obtain minimal forbidden induced subgraphs from critical graphs, even more, we show that the family of graphs obtained using our procedure is exactly the family of VPT minimal forbidden induced subgraphs for [h,2,1]. The members of this family together with the minimal forbidden induced subgraphs for VPT, are the minimal forbidden induced subgraphs for [h,2,1], with h≥3h\geq 3. Notice that by taking h=3 we obtain a characterization by minimal forbidden induced subgraphs of the class VPT ∩\cap EPT=EPT ∩\cap Chordal=[3,2,2]=[3,2,1].

Open access
preprint2011arXiv

Recognizing [h,2,1] graphs

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at mots s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted [h,s,t]. An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. In this paper we characterize [h,2,1] graphs using chromatic number. We show that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete, while the problem of deciding whether the graph belongs to [h,2,1]-[h-1,2,1] is NP-hard. Both problems remain hard even when restricted to Split∩VPTSplit \cap VPT. Additionally, we present a non-trivial subclass of Split∩VPTSplit \cap VPT in which these problems are polynomial time solvable.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.