A new characterization of proper interval graphs (Q1199478): Difference between revisions

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.