Skip to main content
SpringerLink
Log in

The complexity of comparability graph recognition and coloring

Die Komplexität der Erkennung und der Färbung von transitiv orientierbaren Graphen

  • Published:
Computing Aims and scope Submit manuscript

Abstract

Using the notion ofG-decomposition introduced in Golumbic [8, 9], we present an implementation of an algorithm which assigns a transitive orientation to a comparability graph inO(δ·|E|) time andO(|E|) space where δ is the maximum degree of a vertex and |E| is the number of edges. A quotient operation reducing the graph in question and preservingG-decomposition and transitive orientability is shown, and efficient solutions to a number ofNP-complete problems which reduce to polynomial time for comparability graphs are discussed.

Zusammenfassung

Wir verwenden den in Golumbic [8, 9] eingeführten Begriff derG-Zerlegung, um eine Implementierung eines Algorithmus anzugeben, der einem transitiv orientierbaren Graphen eine transitive Orientierung in ZeitO(δ·|E|) und PlatzO(|E|) zuordnet, wobei δ der maximale Grad eines Knoten und |E| die Anzahl der Kanten ist. Wir zeigen eine Quotientenoperation, die den betrachteten Graphen reduziert undG-Zerlegung und transitive Orientierbarkeit bewahrt, und es werden effiziente Lösungen einigerNP-vollständiger Probleme diskutiert, die, für transitiv orientierbare Graphen, in Polynomzeit lösbar sind.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berge, C.: Graphs and Hypergraphs, Chapter 16. Amsterdam: North-Holland 1973.

    Google Scholar 

  2. Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. ACM19, 400–410 (1972).

    Article  Google Scholar 

  3. Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung.18, 25–66 (1967).

    Article  Google Scholar 

  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).

    Article  Google Scholar 

  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).

    Google Scholar 

  6. Gilmore, P. C., Hoffman, A. J.: A characterization of comparability graphs and of interval graphs. Can. J. Math.16, 539–548 (1964).

    Google Scholar 

  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.

  9. Golumbic, M. C.: Comparability graphs and a new matroid. J. Comb. Th., SeriesB 22, 68–90 (1977).

    Google Scholar 

  10. Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math.23, 160–175 (1971).

    Google Scholar 

  11. Shevrin, L. N., Filippov, N. D.: Partially ordered sets and their comparability graphs. Siberian Math. J.11, 497–509 (1970).

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Courant Institute of Mathematics, 251 Mercer Street, 10012, New York, NY, USA

    M. C. Golumbic (Assistant Professor of Computer Science)

Authors
  1. M. C. Golumbic
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by NSF grant DCR-75-09218.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Golumbic, M.C. The complexity of comparability graph recognition and coloring. Computing 18, 199–208 (1977). https://doi.org/10.1007/BF02253207

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02253207

Keywords

Search

Navigation