Hedetniemi's conjecture
Encyclopedia
In graph theory
, Hedetniemi's conjecture, named after Stephen T. Hedetniemi, concerns the connection between graph coloring
and the tensor product of graphs
. This conjecture states that
Here χ(G) denotes the chromatic number of an undirected finite graph G.
An inequality in one direction 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, so χ(G × H) ≤ χ(G). For the same reason χ(G × H) ≤ χ(H); therefore, χ(G × H) ≤ min {χ(G), χ(H)}. Thus, Hedetniemi's conjecture amounts to the assertion that tensor products can't be colored with an unexpectedly small number of colors.
Hedetniemi formulated his conjecture in 1966 based on the inequality described above. Hedetniemi's conjecture has also been called the Lovász
-Hedetniemi conjecture. It cannot be generalized to infinite graphs: gave an example of two infinite graphs, each requiring an uncountable number of colors, such that their product can be colored with only countably many colors.
s Cm and Cn. Then the edges of G × H can be grouped into cycles with length equal to the least common multiple of m and n. Thus, if both G and H have an odd number of vertices and therefore require three colors, the product G × H will contain odd cycles and will also require three colors.
was proven by Sabidussi (1957) and rediscovered several times afterwards. Häggkvist et al. (1988) view graph coloring categorically, as a homomorphism from a graph to a complete graph, and consider similar problems for generalizations of graph coloring involving homomorphisms to incomplete graphs. Duffus et al. (1985) introduced two stronger conjectures involving unique colorability.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Hedetniemi's conjecture, named after Stephen T. Hedetniemi, concerns the connection between graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
and the tensor product of graphs
Tensor product of graphs
In graph theory, the tensor product G × H of graphs G and H is a graph such that* the vertex set of G × H is the Cartesian product V × V; and...
. This conjecture states that
- χ(G × H) = min {χ(G), χ(H)}.
Here χ(G) denotes the chromatic number of an undirected finite graph G.
An inequality in one direction 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, so χ(G × H) ≤ χ(G). For the same reason χ(G × H) ≤ χ(H); therefore, χ(G × H) ≤ min {χ(G), χ(H)}. Thus, Hedetniemi's conjecture amounts to the assertion that tensor products can't be colored with an unexpectedly small number of colors.
Hedetniemi formulated his conjecture in 1966 based on the inequality described above. Hedetniemi's conjecture has also been called the Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
-Hedetniemi conjecture. It cannot be generalized to infinite graphs: gave an example of two infinite graphs, each requiring an uncountable number of colors, such that their product can be colored with only countably many colors.
Example
Suppose that G and H are both cycle graphCycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
s Cm and Cn. Then the edges of G × H can be grouped into cycles with length equal to the least common multiple of m and n. Thus, if both G and H have an odd number of vertices and therefore require three colors, the product G × H will contain odd cycles and will also require three colors.
Special cases
Clearly, any graph with a nonempty set of edges requires two colors; therefore, the conjecture is true whenever G or H is bipartite. It is also true when G or H is 3-colorable, for if both G and H contain an odd cycle then so does G × H. In the remaining cases, both factors of the tensor product require four or more colors. When both factors are 4-chromatic, El-Zahar and Sauer (1985) showed that their tensor product also requires four colors; therefore, Hedetniemi's conjecture is true for this case as well.Related problems
A similar equality for the cartesian product of graphsCartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
was proven by Sabidussi (1957) and rediscovered several times afterwards. Häggkvist et al. (1988) view graph coloring categorically, as a homomorphism from a graph to a complete graph, and consider similar problems for generalizations of graph coloring involving homomorphisms to incomplete graphs. Duffus et al. (1985) introduced two stronger conjectures involving unique colorability.