Recognizing vertex intersection graphs of paths on bounded degree trees

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

zbMATH Keywords

chromatic numberintersection graphsrepresentations on treesVPT graphsrecognition problems

Mathematics Subject Classification ID

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