Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Hedetniemi's conjecture
Summary
In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that
Here denotes the chromatic number of an undirected finite graph .
The inequality χ(G × H) ≤ min {χ(G), χ(H)} is easy: if G is k-colored, one can k-color G × H by using the same coloring for each copy of G in the product; symmetrically if H is k-colored. Thus, Hedetniemi's conjecture amounts to the assertion that tensor products cannot be colored with an unexpectedly small number of colors.
A counterexample to the conjecture was discovered by (see ), thus disproving the conjecture in general.
Any graph with a nonempty set of edges requires at least two colors; if G and H are not 1-colorable, that is, they both contain an edge, then their product also contains an edge, and is hence not 1-colorable either. In particular, the conjecture is true when G or H is a bipartite graph, since then its chromatic number is either 1 or 2.
Similarly, if two graphs G and H are not 2-colorable, that is, not bipartite, then both contain a cycle of odd length. Since the product of two odd cycle graphs contains an odd cycle, the product G × H is not 2-colorable either. In other words, if G × H is 2-colorable, then at least one of G and H must be 2-colorable as well.
The next case was proved long after the conjecture's statement, by : if the product G × H is 3-colorable, then one of G or H must also be 3-colorable. In particular, the conjecture is true whenever G or H is 4-colorable (since then the inequality χ(G × H) ≤ min {χ(G), χ(H)} can only be strict when G × H is 3-colorable).
In the remaining cases, both graphs in the tensor product are at least 5-chromatic and progress has only been made for very restricted situations.
The following function (known as the Poljak-Rödl function) measures how low the chromatic number of products of n-chromatic graphs can be.
Hedetniemi's conjecture is then equivalent to saying that f(n) = n.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.