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

Monthly Archives