Characterizing path graphs by forbidden induced subgraphs

DOI10.1002/JGT.20407zbMath1221.05220arXiv0803.0956OpenAlexW4229740016MaRDI QIDQ3652563

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)

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

zbMATH Keywords

forbidden induced subgraphsintersection graphspath graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items (13)

End simplicial vertices in path graphs ⋮ On models of directed path graphs non rooted directed path graphs ⋮ Characterizing directed path graphs by forbidden asteroids ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Asteroidal quadruples in non rooted path graphs ⋮ Two new characterizations of path graphs ⋮ Reduced clique graphs of chordal graphs ⋮ The vertex leafage of chordal graphs ⋮ Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs ⋮ Intersection graphs of non-crossing paths ⋮ From Path Graphs to Directed Path Graphs ⋮ Asteroids in rooted and directed path graphs ⋮ On some simplicial elimination schemes for chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Some remarks on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A recognition algorithm for the intersection graphs of paths in trees
• The forbidden subgraph characterization of directed vertex graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Algorithmic graph theory and perfect graphs
• A faster algorithm to recognize undirected path graphs
• Intersection representations of graphs by arcs
• 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
• 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
• Topics in Intersection Graph Theory

This page was built for publication: Characterizing path graphs by forbidden induced subgraphs