Article ID Journal Published Year Pages File Type
4653980 European Journal of Combinatorics 2011 8 Pages PDF
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
,