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
1986
0 references
graph coloring
0 references
complexity
0 references
NP-completeness
0 references
0.9365676641464232
0 references
0.8607360124588013
0 references
0.8543297052383423
0 references
0.8543297052383423
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