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.

Statistics

Seen <100 times
0 Comments

More articles like this

On the complexity of recognizing a class of perfec...

on Discrete Applied Mathematics Jan 01, 1996

A note on perfectly orderable graphs

on Discrete Applied Mathematics Jan 01, 1996

New classes of perfectly orderable graphs

on Discrete Mathematics Jan 01, 2001

Which claw-free graphs are perfectly orderable?

on Discrete Applied Mathematics Jan 01, 1993
More articles like this..