Example of Hedetniemi's conjecture: the tensor product of C5 and C3 (on the left) produces a graph that contains a cycle with length 15 (on the right) so: the resulting graph requires 3 colors.
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 YaroslavShitov(2019) (see Kalai 2019), 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 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 has been proved long after the conjecture's statement, by El-Zahar & Sauer (1985): 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.
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 f(n) = n. 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 (Poljak & Rödl 1981), 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 homomorphisms, especially because of interesting relations to the category 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 Kk-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 K1, K2, and K3 are multiplicative. The case of K4 is widely open. On the other hand, the proof of El-Zahar & Sauer (1985) has been generalized by Häggkvist et al. (1988) to show that all cycle graphs are multiplicative. Later, Tardif (2005) proved more generally that all circular cliquesKn/k with n/k < 4 are multiplicative. In terms of the circular chromatic numberχc, this means that if χc(G×H) < 4, then χc(G×H) = min { χc(G), χc(G)} . Wrochna (2017) 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 graphKG is the graph with all functions V(G) → V(K) 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 × K2 (the bipartite double cover of G) to K.
The exponential graph is the exponential object in the category of graphs. This means homomorphisms from G × H to a graph K correspond to homomorphisms from H to KG. Moreover, there is a homomorphism eval: G × KG → K given by eval(v,f) = f(v). These properties allow to conclude that the multiplicativity of K is equivalent (El-Zahar & Sauer 1985) to the statement:
either G or KG 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 KkG is either k-colorable, or it contains a loop (meaning G is k-colorable). One can also see the homomorphisms eval: G × KkG → Kk as the hardest instances of Hedetniemi's conjecture: if the product G × H was a counterexample, then G × KkG would also be a counterexample.
Generalizations
Generalized to directed graphs, the conjecture has simple counterexamples, as observed by Poljak & Rödl (1981). 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 (Tardif & Wehlau 2006).
The problem cannot be generalized to infinite graphs: Hajnal (1985) 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. Rinot (2013) proved that in the constructible universe, 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.
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 are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
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 vertices.
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges and no edge and its endvertices are assigned the same color. The total chromatic number χ″(G) of a graph G is the fewest colors needed in any total coloring of G.
In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number χH(G) of a graph G is the minimum number of colors needed for any harmonious coloring of G.
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned different colors. In a fractional coloring however, a set of colors is assigned to each vertex of a graph. The requirement about adjacent vertices still holds, so if two vertices are joined by an edge, they must have no colors in common.
In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: A000934, the chromatic number or Heawood number.
In graph theory, the Hadwiger conjecture states that if G is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.
In graph theory, the Cartesian productGH of graphs G and H is a graph such that
In graph theory, the tensor productG × H of graphs G and H is a graph such that
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski (1955). The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.
In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it is an assignment of colors to vertices of an oriented graph that
In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the following definitions, all of which are equivalent.
is the infimum over all real numbers so that there exists a map from to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance along this circle.
is the infimum over all rational numbers so that there exists a map from to the cyclic group with the property that adjacent vertices map to elements at distance apart.
In an oriented graph, declare the imbalance of a cycle to be divided by the minimum of the number of edges directed clockwise and the number of edges directed counterclockwise. Define the imbalance of the oriented graph to be the maximum imbalance of a cycle. Now, is the minimum imbalance of an orientation of .
In graph-theoretic mathematics, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.
In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices.
In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph G equals one plus the length of a longest path in an orientation of G chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.
The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.
In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.
In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
References
Primary sources
Duffus, D.; Sands, B.; Woodrow, R. E. (1985), "On the chromatic number of the product of graphs", Journal of Graph Theory, 9 (4): 487–495, doi:10.1002/jgt.3190090409, MR0890239 .
El-Zahar, M.; Sauer, N. (1985), "The chromatic number of the product of two 4-chromatic graphs is 4", Combinatorica, 5 (2): 121–126, doi:10.1007/BF02579374, MR0815577 .
Tardif, C.; Wehlau, D. (2006), "Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function", Journal of Graph Theory, 51 (1): 33–36, doi:10.1002/jgt.20117 .
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
