zbMATH — the first resource for mathematics

Chronological orderings of interval graphs. (English) Zbl 0543.05059
An interval graph is a graph, which is the intersection graph of a set of intervals of the real line. The set of intervals is called an interval representation of the graph. This paper gives three methods for describing the differences of the order of the endpoints of the intervals along the line.
Reviewer: M.Gionfriddo

05C99 Graph theory
Full Text: DOI
[1] Benzer, S., The fine structure of the gene, Sci. amer., 206, 70-84, (1962)
[2] Benzer, S., On the topology of the genetic fine structure, Proc. nat. acad. sci. USA, 45, 1607-1620, (1959)
[3] Gavril, F., A recognition algorithm for the intersection graphs of paths in trees, Discrete math., 23, 211-227, (1978) · Zbl 0398.05060
[4] Gilmore, P.; Hoffman, A., A characterization of comparability graphs and of interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[5] Golumbic, M., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[6] Golumbic, M., Comparability graphs and a new matroid, J. combin. theory, B22, 68-90, (1977) · Zbl 0352.05023
[7] Golumbic, M., The complexity of comparability graph recognition and coloring, Computing, 18, 199-208, (1977) · Zbl 0365.05025
[8] Kendall, D., Incidence matrices, interval graphs and seriation in archaeology, Pacific J. math., 28, 565-570, (1969) · Zbl 0185.03301
[9] Kendall, D., Some problems and methods in statistical archaeology, World archaeology, 1, 68-76, (1969)
[10] Leibowitz, R., Interval counts and threshold graphs, ()
[11] Roberts, F., Discrete mathematical models, with applications to social, biological and environmental problems, (1976), Prentice-Hall Englewood Cliffs NJ · Zbl 0363.90002
[12] Roberts, F., Graph theory and its applications to problems of society, () · Zbl 0452.05001
[13] Skrien, D., Interval graphs, chronological orderings, and related matters, () · Zbl 0543.05059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.