The chromatic Ramsey number of graphs and fractional colouring of product graphs
Presented by Prof. Xuding ZHU
Type: Oral presentation
Track: Coloring of Graphs
This talk sketches a proof that the fractional chromatic number of the categorical product of two graphs is equal to the minimum of the fractional chromatic numbers of the two factor graphs. Using this result, we prove a conjecture of Burr-Erdos-Lovasz concerning the chromatic Ramsey number of graphs: For any positive integer $n$, there is an $n$-chromatic graph $G$ whose chromatic Ramsey number is equal to $(n-1)^2+1$. Here the chromatic Ramsey number of a graph $G$ is the minimum integer $m$ for which there is an $m$-chromatic graph $F$ with the following property: For any $2$-edge colouring of $F$, there is a monochromatic copy of $G$.