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

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.

[1] Edward A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485–515. MR 0376369, https://doi.org/10.1137/1016082
[2] 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/1963), 45–64. MR 0139159, https://doi.org/10.4064/fm-51-1-45-64
[3] Joel Cohen, The probability of a unit interval graph (to appear).
[4] 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
[5] P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964), 539–548. MR 0175811, https://doi.org/10.4153/CJM-1964-055-5
[6] 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
[7] Jerrold R. Griggs, Extremal values of the interval number of a graph. II, Discrete Math. 28 (1979), no. 1, 37–47. MR 542934, https://doi.org/10.1016/0012-365X(79)90183-3
[8] 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, https://doi.org/10.1137/0601001
[9] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
[10] Frank Harary and Jerald A. Kabell, Monotone sequences of graphical invariants, Networks 10 (1980), no. 3, 273–275. MR 584891, https://doi.org/10.1002/net.3230100308
[11] Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
[12] William T. Trotter Jr. and Frank Harary, On double and multiple interval graphs, J. Graph Theory 3 (1979), no. 3, 205–211. MR 542541, https://doi.org/10.1002/jgt.3190030302
[13] 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, https://doi.org/10.2307/2317880
[14] G. Pólya, Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145-254.
[15] F. Roberts, Discrete mathematical models, Prentice-Hall, Englewood Cliffs, N. J., 1976.
[16] -, Graph theory with applications to problems of society, SIAM (1978).
[17] 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