@article{HELL199092,
    Abstract = {Let H be a fixed graph, whose vertices are referred to as `colors'. An H-coloring of a graph G is an assignment of `colors' to the vertices of G such that adjacent vertices of G obtain adjacent `colors'. (An H-coloring of G is just a homomorphism G → H). The following H-coloring problem has been the object of recent interest: Instance: A graph G.Question: Is it possible to H-color the graph G? H-colorings generalize traditional graph colorings, and are of interest in the study of grammar interpretations. Several authors have studied the complexity of the H-coloring problem for various (families of) fixed graphs H. Since there is an easy H-colorability test when H is bipartite, and since all other examples of the H-colorability problem that were treated (complete graphs, odd cycles, complements of odd cycles, Kneser graphs, etc.) turned out to be NP-complete, the natural conjecture, formulated in several sources (including David Johnson's NP-completeness column), asserts that the H-coloring problem is NP-complete for any non-bipartite graph H. We give a proof of this conjecture.},
    Author = {Hell, Pavol and Ne{\v s}et{\v r}il, Jaroslav},
    File = {On the complexity of H-coloring - 1-s2.0-009589569090132J-main.pdf},
    ISSN = {0095-8956},
    Journal = {Journal of Combinatorial Theory, Series B},
    Number = {1},
    Pages = {92-110},
    Title = {On the complexity of H-coloring},
    URL = {https://www.sciencedirect.com/science/article/pii/009589569090132J},
    Volume = {48},
    Year = {1990},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/009589569090132J},
    bdsk-url-2 = {https://doi.org/10.1016/0095-8956(90)90132-J},
    date-added = {2021-07-16 08:13:50 +0200},
    date-modified = {2021-07-16 08:13:50 +0200},
    doi = {10.1016/0095-8956(90)90132-J}
}

@article{HELL199092, Abstract = {Let H be a fixed graph, whose vertices are referred to as colors'. An H-coloring of a graph G is an assignment ofcolors' to the vertices of G such that adjacent vertices of G obtain adjacent `colors'. (An H-coloring of G is just a homomorphism G → H). The following H-coloring problem has been the object of recent interest: Instance: A graph G.Question: Is it possible to H-color the graph G? H-colorings generalize traditional graph colorings, and are of interest in the study of grammar interpretations. Several authors have studied the complexity of the H-coloring problem for various (families of) fixed graphs H. Since there is an easy H-colorability test when H is bipartite, and since all other examples of the H-colorability problem that were treated (complete graphs, odd cycles, complements of odd cycles, Kneser graphs, etc.) turned out to be NP-complete, the natural conjecture, formulated in several sources (including David Johnson's NP-completeness column), asserts that the H-coloring problem is NP-complete for any non-bipartite graph H. We give a proof of this conjecture.}, Author = {Hell, Pavol and Ne{\v s}et{\v r}il, Jaroslav}, File = {On the complexity of H-coloring - 1-s2.0-009589569090132J-main.pdf}, ISSN = {0095-8956}, Journal = {Journal of Combinatorial Theory, Series B}, Number = {1}, Pages = {92-110}, Title = {On the complexity of H-coloring}, URL = {https://www.sciencedirect.com/science/article/pii/009589569090132J}, Volume = {48}, Year = {1990}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/009589569090132J}, bdsk-url-2 = {https://doi.org/10.1016/0095-8956(90)90132-J}, date-added = {2021-07-16 08:13:50 +0200}, date-modified = {2021-07-16 08:13:50 +0200}, doi = {10.1016/0095-8956(90)90132-J} }