The forbidden subgraph characterization of directed vertex graphs

DOI10.1016/S0012-365X(98)00127-7zbMath0928.05029WikidataQ127976741 ScholiaQ127976741MaRDI QIDQ1297413

B. S. Panda

Publication date: 9 January 2000

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

zbMATH Keywords

intersection graphcharacterizationdigraphsforbidden subgraphsdirected path graphdirected vertex graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20)

Related Items (9)

On models of directed path graphs non rooted directed path graphs ⋮ Characterizing directed path graphs by forbidden asteroids ⋮ Characterizing width two for variants of treewidth ⋮ Asteroidal quadruples in non rooted path graphs ⋮ Two new characterizations of path graphs ⋮ Intersection graphs of non-crossing paths ⋮ From Path Graphs to Directed Path Graphs ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ Asteroids in rooted and directed path graphs

Cites Work

• Unnamed Item
• On rigid circuit graphs
• Topics on perfect graphs
• Intersection graphs of paths in a tree
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• A characterisation of rigid circuit graphs
• Intersection graphs of vertex disjoint paths in a tree
• A faster algorithm to recognize undirected path graphs
• Incidence matrices and interval graphs
• Intersection representations of graphs by arcs
• Triangulated graphs and the elimination process
• 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
• Representations of chordal graphs as subtrees of a tree
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: The forbidden subgraph characterization of directed vertex graphs