The intersection graphs of subtrees in trees are exactly the chordal graphs

Journal of Combinatorial Theory, Series B - Tập 16 Số 1 - Trang 47-56 - 1974
Fǎnicǎ Gavril1
1Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

Tóm tắt

Từ khóa


Tài liệu tham khảo

Hajós, 1957, Über eine Art von Graphen, Internat. Math. Nachr., 11, 65

Gilmore, 1964, A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539, 10.4153/CJM-1964-055-5

Lekkerkerker, 1962, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45, 10.4064/fm-51-1-45-64

Fulkerson, 1965, Incidence matrices and intercal graphs, Pacific J. Math., 15, 835, 10.2140/pjm.1965.15.835

Roberts, 1969, Indifference graphs, 139

Kendall, 1969, Incidence matrices, interval graphs, and seriation in archeology, Pacific J. Math., 28, 565, 10.2140/pjm.1969.28.565

Benzer, 1959, On the topology of the genetic fine structure, 45, 1607

J. Cohen, Interaxal graphs and food webs, The RAND Corporation D-17696-PR.

Hadwiger, 1964, Combinatorial Geometry in the Plane, 54

Klee, 1969, What are the intersection graphs of arcs in a circle?, Amer. Math. Monthly, 76, 810, 10.2307/2317880

Tucker, 1971, Matrix characterizations of circular-arc graphs, Pacific J. Math., 38, 535, 10.2140/pjm.1971.39.535

Stahl, 1967, Circular genetic maps, J. Cell. Physiol., 70, 1, 10.1002/jcp.1040700403

Renz, 1970, Intersection representations of graphs by arcs, Pacific J. Math., 34, 501, 10.2140/pjm.1970.34.501

Dirac, 1961, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71, 10.1007/BF02992776

Rose, 1970, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, 10.1016/0022-247X(70)90282-9

Gavril, 1972, Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180, 10.1137/0201013