Counting interval graphs

Hanlon, Phil

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

Counting interval graphs

Author: Phil Hanlon
Journal: Trans. Amer. Math. Soc. 272 (1982), 383-426
MSC: Primary 05C30; Secondary 05-04, 05C75
DOI: https://doi.org/10.1090/S0002-9947-1982-0662044-8
MathSciNet review: 662044
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

Edward A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485–515. MR 376369, DOI https://doi.org/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 https://doi.org/10.4064/fm-51-1-45-64

Joel Cohen, The probability of a unit interval graph (to appear).

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 https://doi.org/10.4153/CJM-1964-055-5
Martin Charles Golumbic, Algorithmic graph theory and perfect graphs, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1980. With a foreword by Claude Berge; Computer Science and Applied Mathematics. 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.2307/2317880

G. Pólya, Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.

F. Roberts, Discrete mathematical models, Prentice-Hall, Englewood Cliffs, N. J., 1976.

---, Graph theory with applications to problems of society, SIAM (1978).

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