×

zbMATH — the first resource for mathematics

The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors. (English) Zbl 1050.05057
Hedetniemi’s conjecture states that \(\chi (G\times H)= \min (\chi (G), \chi (H))\) for any two graphs \(G,H\), where \(G\times H = (V(G)\times V(H)\), \(\{\{(u_1,u_2), (v_1,v_2)\}: \{u_1,v_1\}\in E(G)\), \(\{u_2,v_2\}\in E(H)\})\). This paper proves \( \chi (G\times H) \geq \tfrac 12 \min (\chi _f(G), \chi _f(H)), \) where \(\chi _f(G)\) denotes the fractional chromatic number of \(G\), which equals \(\min \{b/a : G\) can be covered by \(b\) independent sets so that every vertex is covered at least \(a\) times}. The short and beautiful proof uses the correspondence of colorings of \(G\times H\) with homomorphisms of \(H\) into the exponential graph \(K^G_n\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: EuDML