Polynomial graph-colorings

W. Gutjahr, E. Welzl, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    61 Citations (Scopus)


    For directed graphs G and H, we say that G is H-colorable, if there is a graph homomorphism from G into H; that is, there is a mapping f from the vertex set of G into the vertex set of H such that whenever there is an edge (x, y) in G, then (f(x),f(y)) is an edge in H. We introduce a new technique for proving that the H-coloring problem is polynomial time decidable for some fixed graphs H. Among others, this is the case if H is a semipath (a "path" with edges directed in either direction), which was not previously known. We also show the existence of a tree T, for which the T-coloring problem is NP-complete.
    Original languageEnglish
    Pages (from-to)29-45
    JournalDiscrete Applied Mathematics
    Issue number1
    Publication statusPublished - 1992


    Dive into the research topics of 'Polynomial graph-colorings'. Together they form a unique fingerprint.

    Cite this