Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653980 | European Journal of Combinatorics | 2011 | 8 Pages |
Abstract
This paper proves that the fractional version of Hedetniemi’s conjecture is true. Namely, for any graphs GG and HH, χf(G×H)=min{χf(G),χf(H)}χf(G×H)=min{χf(G),χf(H)}. As a by-product, we obtain a proof of the Burr–Erdős–Lovász conjecture: For any positive integer nn, there exists an nn-chromatic graph GG whose chromatic Ramsey number equals (n−1)2+1(n−1)2+1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Xuding Zhu,