×

The complexity of comparability graph recognition and coloring. (English) Zbl 0365.05025


MSC:

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C.: Graphs and Hypergraphs, Chapter 16. Amsterdam: North-Holland 1973. · Zbl 0254.05101
[2] Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. ACM19, 400–410 (1972). · Zbl 0251.05113 · doi:10.1145/321707.321710
[3] Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung.18, 25–66 (1967). · Zbl 0153.26002 · doi:10.1007/BF02020961
[4] Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph. SIAM J. Comp.1, 180–187 (1972). · Zbl 0227.05116 · doi:10.1137/0201013
[5] Ghouila-Houri, A.: Caractérisation des graphes nonorientés dont on peut orienter les arêtes de manière à obtenir le graphe d’une relation d’ordre. C. R. Acad. Sci. Paris254, 1370–1371 (1962). · Zbl 0105.35503
[6] 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 · doi:10.4153/CJM-1964-055-5
[7] Golumbic, M. C.: An infinite class of superperfect noncomparability graphs. IBM Research RC 5064 (October 1974).
[8] Golumbic, M. C.: Comparability graphs and a new matroid (extended abstract). Proc. Alg. Aspects of Comb., Univ. of Toronto, January 1975. · Zbl 0317.05023
[9] Golumbic, M. C.: Comparability graphs and a new matroid. J. Comb. Th., SeriesB 22, 68–90 (1977). · Zbl 0352.05023 · doi:10.1016/0095-8956(77)90049-1
[10] Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math.23, 160–175 (1971). · Zbl 0204.24604 · doi:10.4153/CJM-1971-016-5
[11] Shevrin, L. N., Filippov, N. D.: Partially ordered sets and their comparability graphs. Siberian Math. J.11, 497–509 (1970). · Zbl 0214.23303 · doi:10.1007/BF00967091
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.