![Hdetniemi conjecture example](https://upload.wikimedia.org/wikipedia/commons/3/30/Hdetniemi_conjecture_example.svg)
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, Hedetniemi's conjecture, formulated by
Stephen T. Hedetniemi in 1966, concerns the connection between
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 o ...
and the
tensor product of graphs
In graph theory, the tensor product of graphs and is a graph such that
* the vertex set of is the Cartesian product ; and
* vertices and are adjacent in if and only if
** is adjacent to in , and
** is adjacent to in .
The tensor prod ...
. This conjecture states that
:
Here
denotes the
chromatic number
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 o ...
of an undirected finite graph
.
The inequality χ(''G'' × ''H'') ≤ min 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.
Known cases
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 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 (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s 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 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.
Weak Hedetniemi Conjecture
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 .
The Weak Hedetniemi Conjecture instead states merely that the function ''f''(''n'') is unbounded.
In other words, if the tensor product of two graphs can be colored with few colors, this should imply some bound on the chromatic number of one of the factors.
The main result of , independently improved by Poljak, James H. Schmerl, and Zhu, states that if the function ''f''(''n'') is bounded, then it is bounded by at most 9.
Thus a proof of Hedetniemi's conjecture for 10-chromatic graphs would already imply the Weak Hedetniemi Conjecture for all graphs.
Multiplicative graphs
The conjecture is studied in the more general context of
graph homomorphism
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...
s, especially because of interesting relations to the
category
Category, plural categories, may refer to:
Philosophy and general uses
* Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
*Categories (Peirce)
* ...
of graphs (with graphs as objects and homomorphisms as arrows). For any fixed graph ''K'', one considers graphs ''G'' that admit a homomorphism to ''K'', written ''G'' → ''K''. These are also called ''K''-colorable graphs. This generalizes the usual notion of graph coloring, since it follows from definitions that a ''k''-coloring is the same as a ''K
k''-coloring (a homomorphism into the complete graph on ''k'' vertices).
A graph ''K'' is called multiplicative if for any graphs ''G'', ''H'', the fact that ''G'' × ''H'' → ''K'' holds implies that ''G'' → ''K'' or ''H'' → ''K'' holds.
As with classical colorings, the reverse implication always holds: if ''G'' (or ''H'', symmetrically) is ''K''-colorable, then ''G'' × ''H'' is easily ''K''-colored by using the same values independently of ''H''.
Hedetniemi's conjecture is then equivalent to the statement that each complete graph is multiplicative.
The above known cases are equivalent to saying that ''K
1'', ''K
2'', and ''K
3'' are multiplicative.
The case of ''K
4'' is widely open.
On the other hand, the proof of has been generalized by to show that all cycle graphs are multiplicative.
Later, proved more generally that all
circular cliques ''K
n/k'' with ''n/k < 4'' are multiplicative.
In terms of the
circular chromatic number ''χ''
c, this means that if , then . has shown that square-free graphs are multiplicative.
Examples of non-multiplicative graphs can be constructed from two graphs ''G'' and ''H'' that are not comparable in the homomorphism order (that is, neither ''G''→''H'' nor ''H''→''G'' holds). In this case, letting ''K''=''G''×''H'', we trivially have ''G''×''H''→''K'', but neither ''G'' nor ''H'' can admit a homomorphism into ''K'', since composed with the projection ''K''→''H'' or ''K''→''G'' it would give a contradiction.
Exponential graph
Since the tensor product of graphs is the
category-theoretic product in the category of graphs (with graphs as objects and homomorphisms as arrows), the conjecture can be rephrased in terms of the following construction on graphs ''K'' and ''G''.
The exponential graph is the graph with all functions as vertices (not only homomorphisms) and two functions ''f'',''g'' adjacent when
:''f(v)'' is adjacent to ''g(v')'' in ''K'', for all adjacent vertices ''v'',''v ' '' of ''G''.
In particular, there is a loop at a function ''f'' (it is adjacent to itself) if and only if the function gives a homomorphism from ''G'' to ''K''.
Seen differently, there is an edge between ''f'' and ''g'' whenever the two functions define a homomorphism from ''G'' × ''K''
2 (the
bipartite double cover
In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, cano ...
of ''G'') to ''K''.
The exponential graph is the
exponential object
In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed c ...
in the category of graphs. This means homomorphisms from ''G'' × ''H'' to a graph ''K'' correspond to homomorphisms from ''H'' to ''K
G''.
Moreover, there is a homomorphism given by .
These properties allow to conclude that the multiplicativity of ''K'' is equivalent to the statement:
: either ''G'' or ''K
G'' is ''K''-colorable, for every graph ''G''.
In other words, Hedetniemi's conjecture can be seen as a statement on exponential graphs: for every integer ''k'', the graph ''K
kG'' is either ''k''-colorable, or it contains a loop (meaning ''G'' is ''k''-colorable).
One can also see the homomorphisms as the ''hardest'' instances of Hedetniemi's conjecture: if the product ''G'' × ''H'' was a counterexample, then ''G'' × ''K
kG'' would also be a counterexample.
Generalizations
Generalized to directed graphs, the conjecture has simple counterexamples, as observed by . Here, the chromatic number of a directed graph is just the chromatic number of the underlying graph, but the tensor product has exactly half the number of edges (for directed edges ''g→g' '' in ''G'' and ''h→h' '' in ''H'', the tensor product ''G'' × ''H'' has only one edge, from ''(g,h)'' to ''(g',h')'', while the product of the underlying undirected graphs would have an edge between ''(g,h')'' and ''(g',h)'' as well).
However, the Weak Hedetniemi Conjecture turns out to be equivalent in the directed and undirected settings .
The problem 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. proved that in the
constructible universe
In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It w ...
, for every infinite cardinal
, there exist a pair of graphs of chromatic number greater than
, such that their product can still be colored with only countably many colors.
Related problems
A similar equality for the
cartesian product of graphs Cartesian means of or relating to the French philosopher René Descartes—from his Latinized name ''Cartesius''. It may refer to:
Mathematics
*Cartesian closed category, a closed category in category theory
*Cartesian coordinate system, modern ...
was proven by and rediscovered several times afterwards.
An exact formula is also known for the
lexicographic product of graphs
In graph theory, the lexicographic product or (graph) composition of graphs and is a graph such that
* the vertex set of is the cartesian product ; and
* any two vertices and are adjacent in if and only if either is adjacent with in or ...
.
introduced two stronger conjectures involving unique colorability.
References
;Primary sources
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
;Surveys and secondary sources
*.
*.
*.
*.
*.
*.
External links
A breakthrough in graph theory ''
Numberphile
''Numberphile'' is an educational YouTube channel featuring videos that explore topics from a variety of fields of mathematics. In the early days of the channel, each video focused on a specific number, but the channel has since expanded its s ...
''
{{Disproved conjectures
Graph products
Graph coloring
Disproved conjectures