2021 | OriginalPaper | Buchkapitel
Note on Hedetniemi’s Conjecture and the Poljak-Rödl Function
verfasst von : Xuding Zhu
Erschienen in: 2019-20 MATRIX Annals
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.