Skip to main content

2021 | OriginalPaper | Buchkapitel

Note on Hedetniemi’s Conjecture and the Poljak-Rödl Function

verfasst von : Xuding Zhu

Erschienen in: 2019-20 MATRIX Annals

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Note on Hedetniemi’s Conjecture and the Poljak-Rödl Function
verfasst von
Xuding Zhu
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-62497-2_31