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)

Review text

For a family \(F\) of non-empty sets, an undirected graph \(G\) is an intersection graph for \(F\) if there is a one-to-one correspondence between vertices of \(G\) and the sets of \(F\) such that two vertices in \(G\) are adjacent if and only if the corresponding sets in \(F\) have a non-empty intersection. A graph is a directed vertex graph or a directed path graph if it is the intersection graph of a family of directed paths in a directed tree. The author gives a characterization of directed vertex graphs based on 15 forbidden subgraphs.

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)