Xuding Zhu (朱緒鼎), Fractional Colouring of Product Graphs

Fractional Colouring of Product Graphs
Xuding Zhu (朱緒鼎)
Institute of Mathematics, Zhejiang Normal University, Jinhua, China
2011/4/22 Fri 4PM-5PM

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.

Tags:

Comments are closed.