Closed graphs are proper interval graphs

Abstract

Let G be a connected simple graph. We prove that G is a closed graph if and only if G is a proper interval graph. As a consequence we obtain that there exist linear-time algorithms for closed graph recognition.

Keywords

• closed graphs
• interval graphs
• gröbner bases
• primary 05c25
• secondary 13c05