×

zbMATH — the first resource for mathematics

The intersection graphs of subtrees in trees are exactly the chordal graphs. (English) Zbl 0266.05101

MSC:
05C99 Graph theory
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hajós, G, Über eine art von graphen, Internat. math. nachr., 11, 65, (1957)
[2] Gilmore, P.C; Hoffman, A.J, A characterization of comparability graphs and of interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[3] Lekkerkerker, C.G; Boland, J.Ch, Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[4] Fulkerson, D.R; Gross, O.A, Incidence matrices and intercal graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[5] Roberts, F, Indifference graphs, (), 139-146
[6] Kendall, D.G, Incidence matrices, interval graphs, and seriation in archeology, Pacific J. math., 28, 565-570, (1969) · Zbl 0185.03301
[7] Benzer, S, On the topology of the genetic fine structure, (), 1607-1620 · Zbl 1329.20080
[8] \scJ. Cohen, Interaxal graphs and food webs, The RAND Corporation D-17696-PR.
[9] Hadwiger, H; Debrunner, H; Klee, V, Combinatorial geometry in the plane, (), 54
[10] Klee, V, What are the intersection graphs of arcs in a circle?, Amer. math. monthly, 76, 810-813, (1969)
[11] Tucker, A, Matrix characterizations of circular-arc graphs, Pacific J. math., 38, 535-545, (1971) · Zbl 0226.05125
[12] Stahl, F.W, Circular genetic maps, J. cell. physiol., 70, Suppl. 1, 1-12, (1967)
[13] Renz, P.L, Intersection representations of graphs by arcs, Pacific J. math., 34, 501-510, (1970) · Zbl 0191.55103
[14] Dirac, G.A, On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[15] Rose, D.J, Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[16] Gavril, F, Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM J. comput., 1, 180-187, (1972) · Zbl 0227.05116
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.