Counting interval graphs

Hanlon, Phil

doi:10.1090/S0002-9947-1982-0662044-8

Counting interval graphs
HTML articles powered by AMS MathViewer

by Phil Hanlon PDF

Trans. Amer. Math. Soc. 272 (1982), 383-426 Request permission

Abstract:

In this paper we enumerate interval graphs (up to isomorphism) along with labelled interval graphs, identity interval graphs, transitive interval graphs and various sorts of unit interval graphs. The enumeration makes use of a structural decomposition of interval graphs which leads to a characterization of those interval graphs having a unique interval representation. Several tables are included.

References

Edward A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485–515. MR 376369, DOI 10.1137/1016082
C. G. Lekkerkerker and J. Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962/63), 45–64. MR 139159, DOI 10.4064/fm-51-1-45-64

The probability of a unit interval graph

Joel E. Cohen, János Komlós, and Thomas Mueller, The probability of an interval graph, and why it matters, Relations between combinatorics and other parts of mathematics (Proc. Sympos. Pure Math., Ohio State Univ., Columbus, Ohio, 1978) Proc. Sympos. Pure Math., XXXIV, Amer. Math. Soc., Providence, R.I., 1979, pp. 97–115 (loose errata). MR 525322
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian J. Math. 16 (1964), 539–548. MR 175811, DOI 10.4153/CJM-1964-055-5
Martin Charles Golumbic, Algorithmic graph theory and perfect graphs, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1980. With a foreword by Claude Berge. MR 562306
Jerrold R. Griggs and Douglas B. West, Extremal values of the interval number of a graph, SIAM J. Algebraic Discrete Methods 1 (1980), no. 1, 1–7. MR 563007, DOI 10.1137/0601001
Jerrold R. Griggs and Douglas B. West, Extremal values of the interval number of a graph, SIAM J. Algebraic Discrete Methods 1 (1980), no. 1, 1–7. MR 563007, DOI 10.1137/0601001
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
Frank Harary and Jerald A. Kabell, Monotone sequences of graphical invariants, Networks 10 (1980), no. 3, 273–275. MR 584891, DOI 10.1002/net.3230100308
Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
William T. Trotter Jr. and Frank Harary, On double and multiple interval graphs, J. Graph Theory 3 (1979), no. 3, 205–211. MR 542541, DOI 10.1002/jgt.3190030302
Victor Klee, Research Problems: What Are the Intersection Graphs of Arcs in a Circle?, Amer. Math. Monthly 76 (1969), no. 7, 810–813. MR 1535525, DOI 10.2307/2317880

Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen

68

Discrete mathematical models

Graph theory with applications to problems of society

Fred S. Roberts, Indifference graphs, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) Academic Press, New York, 1969, pp. 139–146. MR 0252267