The forbidden subgraph characterization of directed vertex graphs

DOI10.1016/S0012-365X(98)00127-7zbMATH Open0928.05029WikidataQ127976741 ScholiaQ127976741MaRDI QIDQ1297413FDOQ1297413

Authors B. S. Panda 

Publication date 9 January 2000

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

digraphscharacterizationintersection graphforbidden subgraphsdirected path graphdirected vertex graph

Mathematics Subject Classification ID

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

Recommendations

• A faster algorithm to recognize undirected path graphs
• Interval digraphs: An analogue of interval graphs
• Intersection graphs of short paths in a tree
• Characterizing path graphs by forbidden induced subgraphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A faster algorithm to recognize undirected path graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Incidence matrices and interval graphs
• Intersection graphs of paths in a tree
• Intersection graphs of vertex disjoint paths in a tree
• Intersection representations of graphs by arcs
• On rigid circuit graphs
• Representation of a finite graph by a set of intervals on the real line
• Representations of chordal graphs as subtrees of a tree
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics on perfect graphs
• Triangulated graphs and the elimination process

Cited in

(12)

• Characterizing directed path graphs by forbidden asteroids
• Asteroids in rooted and directed path graphs
• Characterizing width two for variants of treewidth
• On models of directed path graphs non rooted directed path graphs
• Asteroidal quadruples in non rooted path graphs
• Intersection graphs of non-crossing paths
• Characterizing path graphs by forbidden induced subgraphs
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• A forbidden subgraph characterization of some graph classes using betweenness axioms
• Two new characterizations of path graphs
• From path graphs to directed path graphs
• Line graphs of directed graphs. I.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1297413)