# zbMATH — the first resource for mathematics

The forbidden subgraph characterization of directed vertex graphs. (English) Zbl 0928.05029
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.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C75 Structural characterization of families of graphs
Full Text:
##### References:
  ()  Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128  Deitz, P.F., Intersection graph algorithms, TR 84-628, ()  Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ., Hamburg, 25, 71-76, (1961) · Zbl 0098.14703  Fulkerson, D.R.; Gross, O.S., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001  Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101  Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete math., 13, 237-249, (1975) · Zbl 0312.05108  Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-217, (1978) · Zbl 0398.05060  Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054  Lekkerkerker, C.G.; Boland, J.C., Representation of a finite graph by a set of interval on the real line, Fundam. math., 51, 45-64, (1962) · Zbl 0105.17501  Monma, C.L.; Wei, V.K., Intersection graphs of paths in a tree, J. combin. theory ser. B, 41, 141-181, (1986) · Zbl 0595.05062  Panda, B.S.; Mohanty, S.P., Intersection graphs of vertex disjoint paths in a tree, Discrete math., 146, 179-209, (1995) · Zbl 0837.05094  Renz, P.L., Intersection representation of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103  Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602  Rose, D.J.; Tarjan, R.E.; Luekar, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019  Schaffer, A.A., A faster algorithm to recognize undirected path graphs, Discrete appl. math., 43, 261-295, (1993) · Zbl 0770.68096  Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062  Walter, J.L., Representation of chordal graphs as subtress of a tree, J. graph theory, 2, 265-267, (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.