Recognizing vertex intersection graphs of paths on bounded degree trees

DOI10.1016/J.DAM.2013.08.004MaRDI QIDQ741718zbMATH OpenOpenAlexFDO

Authors L. Alcón, M. Gutierrez, M. P. Mazzoleni

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 graphsrecognition problemsrepresentations on treesVPT graphs

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. II
• Edge and vertex intersection of paths in a tree
• Graphs of edge-intersecting non-splitting paths in a tree: towards hole representations (extended abstract)

Cites work

• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Connectivity threshold for random chordal graphs
• Constant tolerance intersection graphs of subtrees of a tree
• Edge and vertex intersection of paths in a tree
• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• Intersection graphs of paths in a tree
• Intersection models of weakly chordal graphs
• Reducibility among combinatorial problems
• Representing edge intersection graphs of paths on degree 4 trees
• The k-edge intersection graphs of paths in a tree
• The ellipsoid method and its consequences in combinatorial optimization
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The strong perfect graph theorem
• Tolerance intersection graphs on binary trees with constant tolerance 3
• Tree representations of graphs
• Triangulated edge intersection graphs of paths in a tree
• What Is between Chordal and Weakly Chordal Graphs?

Cited in

(5)

• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Constant threshold intersection graphs of orthodox paths in trees
• Intersection graphs of orthodox paths in trees
• Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
• Relationship among B₁-EPG, VPT and EPT graphs classes

This page was built for publication: Recognizing vertex intersection graphs of paths on bounded degree trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741718)