Characterizing path graphs by forbidden induced subgraphs
From MaRDI portal
Abstract: A graph is a path graph if it is the intersection graph of a family of subpaths of a tree. In 1970, Renz asked for a characterizaton of path graphs by forbidden induced subgraphs. Here we answer this question by listing all graphs that are not path graphs and are minimal with this property.
Recommendations
Cites work
- A faster algorithm to recognize undirected path graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- scientific article; zbMATH DE number 3152801 (Why is no real title available?)
- scientific article; zbMATH DE number 5158514 (Why is no real title available?)
- scientific article; zbMATH DE number 3912430 (Why is no real title available?)
- Intersection representations of graphs by arcs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On rigid circuit graphs
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Some remarks on interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The forbidden subgraph characterization of directed vertex graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Topics in Intersection Graph Theory
Cited in
(26)- The forbidden subgraph characterization of directed vertex graphs
- A forbidden subgraph characterization of some graph classes using betweenness axioms
- The vertex leafage of chordal graphs
- End simplicial vertices in path graphs
- Intersection graphs of short paths in a tree
- Asteroids in rooted and directed path graphs
- On some simplicial elimination schemes for chordal graphs
- On models of directed path graphs non rooted directed path graphs
- Contraction Blockers for Graphs with Forbidden Induced Paths
- From path graphs to directed path graphs
- Characterizing directed path graphs by forbidden asteroids
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
- A characterization of substar graphs
- Reduced clique graphs of chordal graphs
- A matrix characterization of induced paths in bridge graphs
- Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
- Intersection graphs of non-crossing paths
- Two new characterizations of path graphs
- scientific article; zbMATH DE number 7731182 (Why is no real title available?)
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Exactly hittable interval graphs
- On paths avoding forbidden pairs of vertices in a graph
- Relationship among B₁-EPG, VPT and EPT graphs classes
- Simpler and unified recognition algorithm for path graphs and directed path graphs
- Asteroidal quadruples in non rooted path graphs
This page was built for publication: Characterizing path graphs by forbidden induced subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652563)
