×

On the complexity of recognizing perfectly orderable graphs. (English) Zbl 0706.68058

Summary: The question whether a polynomial time recognition algorithm for the class of perfectly orderable graphs exists was posed by V. Chvátal in [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] 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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory

Citations:

Zbl 0559.05055
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chvátal, V.; Berge, C.; Chvátal, V., Perfectly ordered graphs, Topics on Perfect Graphs, 21, 253-272 (1984), Ann. Discrete Math. · Zbl 0559.05055
[2] Ghouila-Houri, A., Caractérisation des graphes non orientés dont on peut orienter les arĕtes de maniére a obtenir le graphe d’une relation d’ordre, C.R. Acad. Sci. Paris, 254, 1370-1371 (1962) · Zbl 0105.35503
[3] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Can. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[4] Hoàng, C. T.; Reed, B. A.; Werra, D.de; Hertz, A., \(P_4\)-comparability graphs, Graph coloring and its application, 74, 173-200 (1989), Ann. Discrete Math. · Zbl 0675.05067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.