Hedetniemi's conjecture and the retracts of a product of graphs

Citation
B. Larose et C. Tardif, Hedetniemi's conjecture and the retracts of a product of graphs, COMBINATORI, 20(4), 2000, pp. 531-544
Citations number
18
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683 → ACNP
Volume
20
Issue
4
Year of publication
2000
Pages
531 - 544
Database
ISI
SICI code
0209-9683(2000)20:4<531:HCATRO>2.0.ZU;2-T
Abstract
We show that every core graph with a primitive automorphism group has the p roperty that whenever it is a retract of a, product of connected graphs, it is a retract of a factor. The example of Kneser graphs shows that the hypo thesis that the factors are connected is essential. In the case of complete graphs, our result has already been shown in [4,17], and it is an instance where Hedetniemi's conjecture is known to hold. In fact, our work is motiv ated by a reinterpretation of Hedetniemi's conjecture in terms of products and retracts.