Affordable Access

Publisher Website

On the complexity of recognizing perfectly orderable graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
80
Issue
3
Identifiers
DOI: 10.1016/0012-365x(90)90251-c
Disciplines
  • Computer Science

Abstract

Abstract The question whether a polynomial time recognition algorithm for the class of perfectly orderable graphs exists was posed by Chvátal in 1981 when he introduced the notion of perfect orders. Since then several classes of perfectly orderable graphs have been identified. In this note we prove that recognizing perfectly orderable graphs is NP-complete.

There are no comments yet on this publication. Be the first to share your thoughts.