A new characterization of proper interval graphs (Q1199478)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new characterization of proper interval graphs |
scientific article |
Statements
A new characterization of proper interval graphs (English)
0 references
16 January 1993
0 references
Intersection graphs of families of intervals, with no interval of the family containing another one, are called proper interval graphs. A slight modification of the well-known notion of `asteroidal triple' leads to the following definition: Three vertices of a graph form an astral triple if any two of them are connected by some path such that the closed neighborhood of the third vertex does not contain two consecutive vertices of the path. The following analogue of the famous asteroidal triple characterization of interval graphs by \textit{C. G. Lekkerkerker} and \textit{J. Ch. Boland} [Fund. Math. 51, 45-64 (1962; Zbl 0105.175)] is proven: A finite graph is a proper interval graph if and only if it contains no astral triple.
0 references
proper interval graphs
0 references
astral triple
0 references
asteroidal triple
0 references
0 references