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 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 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 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
Additional Information
- © Copyright 1982 American Mathematical Society
- 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