Hedetniemi's conjecture

Hedetniemi's conjecture

In graph theory, Hedetniemi's conjecture concerns the connection between graph coloring and the tensor product of graphs. 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.

S. 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: 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.

Example

Suppose that "G" and "H" are both cycle graphs "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 graphs 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.

References

*cite journal
author = Duffus, D.; Sands, B.; Woodrow, R. E.
title = On the chromatic number of the product of graphs
journal = J. Graph Theory
volume = 9
year = 1985
issue = 4
pages = 487–495
id = MathSciNet | id = 0890239
doi = 10.1002/jgt.3190090409

*cite journal
author = El-Zahar, M.; Sauer, N.
title = The chromatic number of the product of two 4-chromatic graphs is 4
journal = Combinatorica
volume = 5
pages = 121–126
year = 1985
id = MathSciNet | id = 0815577
doi = 10.1007/BF02579374

*cite journal
author = Häggkvist, R.; Hell, P.; Miller, D. J.; Neumann Lara, V.
title = On multiplicative graphs and the product conjecture
journal = Combinatorica
volume = 8
year = 1988
issue = 1
pages = 63–74
id = MathSciNet | id = 0951994
doi = 10.1007/BF02122553

*cite journal
author = Hajnal, A.
title = The chromatic number of the product of two ℵ1 chromatic graphs can be countable
journal = Combinatorica
volume = 5
year = 1985
pages = 137–140
id = MathSciNet | id = 0815579
doi = 10.1007/BF02579376

*cite paper
author = S. Hedetniemi
title = Homomorphisms of graphs and automata
version = Technical Report 03105-44-T
date = 1966
publisher = University of Michigan

*cite book
author = Imrich, Wilfried; Klavžar, Sandi
title = Product Graphs: Structure and Recognition
publisher = Wiley
year = 2000
id = ISBN 0-471-37039-8

*cite journal
author = Klavžar, Sandi
title = Coloring graph products: a survey
journal = Discrete Mathematics
volume = 155
year = 1996
issue = 1–3
pages = 135–145
id = MathSciNet | id = 1401366
doi = 10.1016/0012-365X(94)00377-U

*cite journal
author = Sabidussi, G.
title = Graphs with given group and given graph-theoretical properties
journal = Canad. J. Math.
volume = 9
year = 1957
pages = 515–525
id = MathSciNet | id = 0094810

*cite journal
author = Sauer, N.
title = Hedetniemi's conjecture: a survey
journal = Discrete Mathematics
volume = 229
issue = 1–3
year = 2001
pages = 261–292
doi = 10.1016/S0012-365X(00)00213-2
id = MathSciNet | id = 1815610

*cite journal
author = Zhu, Xuding
title = A survey on Hedetniemi's conjecture
journal = Taiwanese J. Math.
volume = 2
year = 1998
issue = 1
pages = 1–24
id = MathSciNet | id = 1609464


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Combinatorica — is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors in chief with Paul Erdős as honorary editor in chief. The… …   Wikipedia

  • Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… …   Wikipedia

  • Cartesian product of graphs — In graph theory, the cartesian product G ◻ H of graphs G and H is a graph such that * the vertex set of G ◻ H is the cartesian product V(G) × V(H) ; and * any two vertices (u,u ) and (v,v ) are adjacent in G ◻ H if and only if either ** u = v and …   Wikipedia

  • 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(G) × V(H) ; and * any two vertices (u,u ) and (v,v ) are adjacent in G × H if and only if u is adjacent with v… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”