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

This entry was posted on Tuesday, March 22nd, 2011 at 10:08 pm and is filed under 2011, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.