# Counterexamples to Hedetniemi's conjecture

@article{Shitov2019CounterexamplesTH, title={Counterexamples to Hedetniemi's conjecture}, author={Yaroslav Shitov}, journal={Annals of Mathematics}, year={2019} }

The chromatic number of $G\times H$ can be smaller than the minimum of the chromatic numbers of finite simple graphs $G$ and $H$.

#### Paper Mentions

#### 40 Citations

Hedetniemi's conjecture is asymptotically false

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2021

It is proved that there exists an absolute constant $\delta>0$ such that for all $c$ sufficiently large, there exist graphs G and H with chromatic number at least $(1+\delta)c$ for which $\chi(G \times H) \le c$. Expand

COUNTEREXAMPLES TO HEDETNIEMI’S CONJECTURE AND INFINITE BOOLEAN LATTICES

- 2021

We prove that for any c ≥ 5, there exists an infinite family (Gn)n∈N of graphs such that χ(Gn) > c for all n ∈ N and χ(Gm×Gn) ≤ c for all m 6= n. These counterexamples to Hedetniemi’s conjecture show… Expand

Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs

- Computer Science, Mathematics
- SIAM J. Comput.
- 2021

For a fixed graph $H$, by Hom($H$) we denote the computational problem which asks whether a given graph $G$ admits a homomorphism to $H$, i.e., an edge-preserving mapping from $V(G)$ to $V(H)$. As ...

On the r-dynamic coloring of the direct product of a path with either a path or a cycle

- Mathematics
- 2020

In this paper, we determine explicitly the r-dynamic chromatic number of the direct product of any given path with either a path or a cycle. Illustrative examples are shown for each one of the cases… Expand

THE CHROMATIC NUMBER OF THE PRODUCT OF 14-CHROMATIC GRAPHS CAN BE 13

- 2020

We show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to… Expand

An algebraic reduction of Hedetniemi's conjecture

- Mathematics
- 2019

For a graph $G$, let $\chi (G)$ denote the chromatic number. In graph theory, the following famous conjecture posed by Hedetniemi has been studied: For two graphs $G$ and $H$, $\chi (G\times… Expand

Quantum multiplicative graph and a type of separate clique number

- Mathematics
- 2021

Abstract In 2013, C. Godsil introduced the quantum version of Hedetniemi’s conjecture. To solve this conjecture, we introduce the concept of quantum multiplicative graph and obtain a necessary and… Expand

A complexity problem for Borel graphs

- Mathematics
- 2017

We show that there is no simple (e.g. finite or countable) basis for Borel graphs with infinite Borel chromatic number. In fact, it is proved that the closed subgraphs of the shift graph on… Expand

A Note on Hedetniemi's Conjecture, Stahl's Conjecture and the Poljak-Rödl Function

- Mathematics, Computer Science
- Electron. J. Comb.
- 2019

It is proved that $\min(G), \chi (H) - \chi(G\times H)$ can be arbitrarily large, and that if Stahl's conjecture on the multichromatic number of Kneser graphs holds, then $\min{G, H}/(\chi(H) \leq 1/2 + \epsilon$ for large values of $\min\(G, \chi)$. Expand

Minimal definable graphs of definable chromatic number at least three

- Mathematics
- Forum of Mathematics, Sigma
- 2021

Abstract We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel… Expand

#### References

SHOWING 1-10 OF 21 REFERENCES

Hedetniemi's conjecture for uncountable graphs

- Mathematics
- 2013

It is proved that in Godel's constructible universe, for every infinite successor cardinal k, there exist graphs G and H of size and chromatic number k, for which the tensor product graph (G x H) is… Expand

Hedetniemi's conjecture -- a survey

- Computer Science, Mathematics
- Discret. Math.
- 2001

This survey article deals with several ramifications of the conjecture that the chromatic number of the product of two graphs is min {χ(G), χ(H)}. Expand

A SURVEY ON HEDETNIEMI'S CONJECTURE

- Mathematics
- 1998

More than 30 years ago, Hedetniemi made a conjecture which says that the categorical product of two n-chromatic graphs is still n-chromatic. The conjecture is still open, despite many dierent… Expand

The chromatic number of the product of two ℵ1-chromatic graphs can be countable

- Mathematics
- 1985

We prove (in ZFC) that for every infinite cardinal ϰ there are two graphsG0,G1 with χ(G0)=χ(G1)=ϰ+ and χ(G0×G1)=ϰ. We also prove a result from the other direction. If χ(G0)≧≧ℵ0 and χ(G1)=k

The fractional version of Hedetniemi's conjecture is true

- Computer Science, Mathematics
- Eur. J. Comb.
- 2011

This paper proves that the fractional version of Hedetniemi's conjecture is true, and obtains a proof of the Burr-Erdos-Lovasz conjecture: For any positive integer n, there exists an n-chromatic graph G whose chromatic Ramsey number equals (n-1)+1. Expand

On the arc-chromatic number of a digraph

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 1981

Using the notion of arc-coloring some remarks concerning the chromatic number of a products of two graphs, or of a product of two digraphs, are proved. Expand

Hedetniemi's conjecture for Kneser hypergraphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2016

It is proved that Zhu's conjecture is true for the usual Kneser hypergraphs of same rank, providing the first non-trivial and explicit family of hyper graphs with rank larger than two satisfying Hedetniemi's conjecture. Expand

Coloring graph products - A survey

- Computer Science, Mathematics
- Discret. Math.
- 1996

The chromatic number turned out to be an interesting parameter on all these products, except on the Cartesian one, and some applications of product colorings are also included. Expand

On inverse powers of graphs and topological implications of Hedetniemi's conjecture

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2019

It is shown that if Hedetniemi's conjecture on the chromatic number of graph products were true for n-colorings, then the following analogous conjecture in topology would also also true: If X,Y are $\mathbb{Z}_2$-spaces such that X x Y admits a $\Mathbb{ Z}_ 2$-map to the (n-2)-dimensional sphere, then X or Y itself admits such a map. Expand

Symmetric graphs and interpretations

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1984

The position of symmetric graphs in this geography of graphs is investigated and the mechanism of interpretation (subgraph homomorphism, homomorphic embedding, general coloring) is investigated. Expand