2021 | OriginalPaper | Chapter
Note on Hedetniemi’s Conjecture and the Poljak-Rödl Function
Author : Xuding Zhu
Published in: 2019-20 MATRIX Annals
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Hedetniemi conjectured in 1966 that Hedetniemi conjectured in 1966 that $$\chi(G \times H) = \min\{\chi(G), \chi(H)\}$$ χ ( G × H ) = min { χ ( G ) , χ ( H ) } for any graphs G and H. Here $$G\times H$$ G × H is the graph with vertex set $$V(G)\times V(H)$$ V ( G ) × V ( H ) defined by putting $$(x,y)$$ ( x , y ) and $$(x^{\prime}, y^{\prime})$$ ( x ′ , y ′ ) adjacent if and only if $$xx^{\prime}\in E(G)$$ x x ′ ∈ E ( G ) and $$yy^{\prime}\in V(H)$$ y y ′ ∈ V ( H ) . This conjecture received a lot of attention in the past half century. It was disproved recently by Shitov. The Poljak-Rodl function is defined as $$f(n) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}$$ f ( n ) = min { χ ( G × H ) : χ ( G ) = χ ( H ) = n } . Hedetniemi's conjecture is equivalent to saying $$f(n)=n$$ f ( n ) = n for every integer $$n$$ n . Shitov’s result shows that $$f(n)<n$$ f ( n ) < n when $$n$$ n is sufficiently large. Using Shitov’s result, Tardif and Zhu showed that $$f(n) \le n - (\log n)^{1/4-o(1)}$$ f ( n ) ≤ n - ( log n ) 1 / 4 - o ( 1 ) for sufficiently large $$n$$ n . Using Shitov’s method, He and Wigderson showed that for $$\epsilon \approx 10^{-9}$$ ϵ ≈ 10 - 9 and $$n$$ n sufficiently large, $$f(n) \le (1-\epsilon)n$$ f ( n ) ≤ ( 1 - ϵ ) n . In this note we observe that a slight modification of the proof in the paper of Zhu and Tardif shows that $$f(n) \le (\frac 12 + o(1))n$$ f ( n ) ≤ ( 1 2 + o ( 1 ) ) n for sufficiently large $$n$$ n . On the other hand, it is unknown whether $$f(n)$$ f ( n ) is bounded by a constant. However, we do know that if $$f(n)$$ f ( n ) is bounded by a constant, then the smallest such constant is at most 9. This note gives self-contained proofs of the above mentioned results.