A survey on Hedetniemi's conjecture
type: Item
instance of: scholarly article
title: A survey on Hedetniemi's conjecture
zbMATH Open document ID: 0906.05024
author: Xuding Zhu
published in: Taiwanese Journal of Mathematics
publication date: 1999-02-14T00:00:00Z
review text: The product \(G\times H\) of the graphs \(G\) and \(H\) has vertex set \[ V(G\times H)= \{(g, h)\mid g\in V(G)\text{ and }h\in V(H)\} \] and edge set \[ E(G\times H)= \{(g, h)(g', h')\mid gg'\in E(G)\text{ and }hh'\in E(H)\}. \] It is easily seen that \(\chi(G\times H)\leq \min\{\chi(G), \chi(H)\}\); \textit{Hedetniemi} [University of Michigan Technical Report 03105-44-T (1966)] conjectured that equality holds for all finite simple graphs \(G\) and \(H\). An equivalent formulation is given by \(C(n)\): If graphs \(G\) and \(H\) are not \(n\)-colorable then the product \(G\times H\) is not \(n\)-colorable. Hedetniemi [ibid.] proved \(C(2)\). \textit{M. El-Zahar} and \textit{N. W. Sauer} [Combinatorica 5, 121-126 (1985; Zbl 0575.05028)] gave a complicated proof of \(C(3)\); the conjecture is open for \(n\geq 4\). The author gives a somewhat simplified version of their proof and then discusses results and problems related to the conjecture.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1160425
zbMATH Keywords: Hedetniemi's conjecture
zbMATH Keywords: \(n\)-colorable
reviewed by: R. C. Entringer
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.11650/twjm/1500406890
OpenAlex ID: W1483461381
Wikidata QID: Q123154756
DOI: 10.11650/TWJM/1500406890
description: scientific article; zbMATH DE number 1160425