Title | ||
---|---|---|
Helly EPT graphs on bounded degree trees: forbidden induced subgraphs and efficient recognition. |
Abstract | ||
---|---|---|
edge intersection graph of a family of paths in host tree is called an $EPT$ graph. When the host tree has maximum degree $h$, we say that $G$ belongs to the class $[h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then $G in$ Helly $[h,2,2]$. The time complexity of the recognition of the classes inside the class $EPT$ is open for every $hu003e 4$. Golumbic et al. wonder if the only obstructions for an $EPT$ graph belonging to $[h,2,2]$ are the chordless cycles $C_n$ for $nu003e h$. In the present paper, we give a negative answer to that question, we present a family of $EPT$ graphs which are forbidden induced subgraphs for the classes $[h,2,2]$. Using them we obtain a total characterization by induced forbidden subgraphs of the classes Helly $[h,2,2]$ for $hgeq 4$ inside the class $EPT$. As a byproduct, we prove that Helly $EPT$$cap [h,2,2]=$ Helly $[h,2,2]$. We characterize Helly $[h,2,2]$ graphs by their atoms in the decomposition by clique separators. We give an efficient algorithm to recognize Helly $[h,2,2]$ graphs. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Combinatorics | Discrete mathematics,Graph,Combinatorics,Intersection graph,Clique separators,Negative - answer,Degree (graph theory),Time complexity,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1604.08775 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Liliana Alcón | 1 | 59 | 14.43 |
Marisa Gutierrez | 2 | 41 | 12.90 |
M. P. Mazzoleni | 3 | 12 | 4.05 |