Characterizing path graphs by forbidden induced subgraphs
From MaRDI portal
Publication:3652563
DOI10.1002/JGT.20407zbMATH Open1221.05220arXiv0803.0956OpenAlexW4229740016MaRDI QIDQ3652563FDOQ3652563
Authors: Benjamin Lévêque, Frédéric Maffray, Myriam Preissmann 
Publication date: 18 December 2009
Published in: Journal of Graph Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0803.0956
Recommendations
Cites Work
- Topics in Intersection Graph Theory
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithmic graph theory and perfect graphs
- On rigid circuit graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- 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
- Title not available (Why is that?)
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- The forbidden subgraph characterization of directed vertex graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Some remarks on interval graphs
- A faster algorithm to recognize undirected path graphs
- Intersection representations of graphs by arcs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (23)
- A characterization of substar graphs
- End simplicial vertices in path graphs
- A matrix characterization of induced paths in bridge graphs
- On models of directed path graphs non rooted directed path graphs
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Exactly hittable interval graphs
- Reduced clique graphs of chordal graphs
- Two new characterizations of path graphs
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Asteroidal quadruples in non rooted path graphs
- Intersection graphs of non-crossing paths
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
- Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs
- A forbidden subgraph characterization of some graph classes using betweenness axioms
- On paths avoding forbidden pairs of vertices in a graph
- From path graphs to directed path graphs
- Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
- On some simplicial elimination schemes for chordal graphs
- The vertex leafage of chordal graphs
- Intersection graphs of short paths in a tree
- Asteroids in rooted and directed path graphs
- Title not available (Why is that?)
- Characterizing directed path graphs by forbidden asteroids
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)
