A note on the Poljak-Rödl function

DOI10.37236/9371MaRDI QIDQ782938zbMATH OpenOpenAlexFDO

Authors Xuding Zhu

Publication date 29 July 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9371

zbMATH Keywords

categorical productexponential graphtensor product

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Review text

Summary: The Poljak-Rödl function is defined as \(f(c) = \min\{\chi(G \times H): \chi(G)=\chi(H)=n\}\). This note proves that \(\lim_{c \to \infty} \frac{f(c)}{c} \leqslant \frac 12\).

Cites work

• A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
• A survey on Hedetniemi's conjecture
• Coloring graph products---a survey
• Counterexamples to Hedetniemi's conjecture
• Hedetniemi's conjecture---a survey
• scientific article; zbMATH DE number 37867 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• n-tuple colorings and associated graphs
• The chromatic number of the product of two 4-chromatic graphs is 4
• The fractional version of Hedetniemi's conjecture is true

Cited in

(6)

• Note on Hedetniemi's conjecture and the Poljak-Rödl function
• Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers
• The chromatic number of the product of 14-chromatic graphs can be 13
• Relatively small counterexamples to Hedetniemi's conjecture
• Shannon capacity and the categorical product
• Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

This page was built for publication: A note on the Poljak-Rödl function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782938)