University of Calgary

Hedetniemi's Conjecture-a survey


What is the chromatic number of the product of two graphs? The conjecture of Hedetniemi [1], which is more than 30 years old, is: $$ \chi(\fract{G}\times \fract{H})=\min\{\chi({\fract G}),\chi({\fract H})\}. $$ This survey article deals with several ramifications of this rather innocent looking question.
Powered by UNITIS. More features.