Hedetniemi's conjecture

Hedetniemi's conjecture asserted that the categorical product of two graphs has chromatic number equal to the smaller chromatic number of its factors. Shitov disproved it for general graphs in 2019.

Connect

Categorical product of graphs: A graph product whose vertices are pairs and whose edges join pairs adjacent in both coordinate graphs. This is the product operation whose chromatic number the conjecture sought to determine.
Stanisław Hedetniemi: An American mathematician known for work in graph theory and computational complexity. He proposed the chromatic-number equality that became the conjecture's namesake.
Counterexample: An example that disproves a universal mathematical statement. A finite pair of graphs with a smaller product chromatic number refutes the conjecture.
Shitov's bound: A lower threshold on the factor chromatic numbers in Shitov's construction of counterexamples. The original disproof used very large chromatic numbers, leaving smaller cases open.
Graph coloring: An assignment of colors to graph vertices such that adjacent vertices receive different colors. The conjecture compares the minimum numbers of colors needed before and after taking a product.
Graph theory: The branch of mathematics that studies graphs and their properties. The conjecture arose within graph theory's study of coloring and graph products.
Shitov's counterexample: A pair of finite graphs whose categorical product has chromatic number below that of both factors. This construction supplied the first disproof of the general conjecture.
Hedetniemi's conjecture for finite graphs: The claim that the categorical-product chromatic equality holds when both factors are finite graphs. The conjecture is false even in the finite setting, through Shitov's construction.
Chromatic number: The minimum number of colors required for a proper coloring of a graph. It is the invariant predicted to equal the smaller factor's value.
Graph products: Operations that construct new graphs from pairs or families of graphs. The categorical product is one of several graph products whose invariants mathematicians compare.