Recognizing vertex intersection graphs of paths on bounded degree trees
From MaRDI portal
Publication:741718
DOI10.1016/j.dam.2013.08.004zbMath1300.05190OpenAlexW2017788065MaRDI QIDQ741718
María Pía Mazzoleni, Liliana Alcón, Marisa Gutierrez
Publication date: 12 September 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://sedici.unlp.edu.ar/handle/10915/85561
Trees (05C05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Intersection graphs of orthodox paths in trees ⋮ Constant threshold intersection graphs of orthodox paths in trees ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
Cites Work
- Unnamed Item
- The strong perfect graph theorem
- Tree representations of graphs
- Equivalences and the complete hierarchy of intersection graphs of paths in a tree
- Intersection models of weakly chordal graphs
- Edge and vertex intersection of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
- Intersection graphs of paths in a tree
- The ellipsoid method and its consequences in combinatorial optimization
- Connectivity threshold for random chordal graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Constant tolerance intersection graphs of subtrees of a tree
- Tolerance intersection graphs on binary trees with constant tolerance 3
- A faster algorithm to recognize undirected path graphs
- The \(k\)-edge intersection graphs of paths in a tree
- Representing edge intersection graphs of paths on degree 4 trees
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Graph Classes: A Survey
- Reducibility among Combinatorial Problems
- What Is between Chordal and Weakly Chordal Graphs?
This page was built for publication: Recognizing vertex intersection graphs of paths on bounded degree trees