The forbidden subgraph characterization of directed vertex graphs

DOI10.1016/S0012-365X(98)00127-7MaRDI QIDQ1297413zbMATH OpenWikidataFDO

Authors B. S. Panda

Publication date 9 January 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(98)00127-7

zbMATH Keywords

characterizationdigraphsdirected path graphdirected vertex graphforbidden subgraphsintersection 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

• 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
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• 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)

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

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)