zbMATH — the first resource for mathematics

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

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.