## 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: