No label defined (Q3758852)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4008418
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4008418

      Statements

      0 references
      0 references
      1986
      0 references
      graph coloring
      0 references
      complexity
      0 references
      NP-completeness
      0 references
      [For the entire collection see Zbl 0608.00004.] 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 in G are assigned ''adjacent colors'' (in H). We have an associated problem: H-coloring - Instance: a graph G, Question: is G H-colorable? Note that the traditional coloring problem is obtained when H is taken to be a complete graph. Since there is an easy H-colorability test when H is bipartite the conjecture was put forward that H-coloring is NP-complete for non-bipartite H. The authors claim to have proven that conjecture.
      0 references

      Identifiers