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.

05C20 Directed graphs (digraphs), tournaments
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] ()
[2] Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[3] Deitz, P.F., Intersection graph algorithms, TR 84-628, ()
[4] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ., Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[5] Fulkerson, D.R.; Gross, O.S., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[6] 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
[7] Gavril, F., A recognition algorithm for the intersection graphs of directed paths in directed trees, Discrete math., 13, 237-249, (1975) · Zbl 0312.05108
[8] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-217, (1978) · Zbl 0398.05060
[9] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[10] 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
[11] 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
[12] Panda, B.S.; Mohanty, S.P., Intersection graphs of vertex disjoint paths in a tree, Discrete math., 146, 179-209, (1995) · Zbl 0837.05094
[13] Renz, P.L., Intersection representation of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103
[14] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[15] 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
[16] Schaffer, A.A., A faster algorithm to recognize undirected path graphs, Discrete appl. math., 43, 261-295, (1993) · Zbl 0770.68096
[17] 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
[18] 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.