Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs

DOI10.1016/j.disc.2014.08.020zbMath1301.05194arXiv1307.2139OpenAlexW2063450788MaRDI QIDQ468443

Marisa Gutierrez, Liliana Alcón, María Pía Mazzoleni

Publication date: 7 November 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.2139

zbMATH Keywords

critical graphsintersection graphsforbidden subgraphsrepresentations on treesVPT graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Constant threshold intersection graphs of orthodox paths in trees

Cites Work

• Unnamed Item
• Recognizing vertex intersection graphs of paths on bounded degree trees
• Edge and vertex intersection of paths in a tree
• Intersection graphs of paths in a tree
• 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
• Representing edge intersection graphs of paths on degree 4 trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Characterizing path graphs by forbidden induced subgraphs
• Graph Classes: A Survey

This page was built for publication: Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs