KAIST Discrete Math Seminar

Given two graphs G and H, the categorical product \(G \times H\) has vertex set \(V(G) \times V(H)\), and two vertices (x,y) and (x’,y’) are adjacent if \(xx’ \in E(G)\) and \(yy’ \in E(H)\). The famous Hedetniemi-Lovász Conjecture asserts that teh chromatic number of \(G \times H\) equals the minimum of \(\chi(G)\) and \(\chi(H)\). In this talk, I will sketch a proof of the fractional version of the conjecture, which says that the fractional chromatic number of \(G \times H\) equals to the minimum of the fractional chromatic numbers of G and H. This result is then used to prove a conjecture of Burr-Erdős-Lovász on the chromatic Ramsey number of graphs.