𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approach to hedetniemi's conjecture

✍ Scribed by N. W. Sauer; X. Zhu

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
717 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a fixed integer n ϵ ω, a graph G of chromatic number greater than n is called persistent if for all n + 1‐chromatic graphs H, the products G × H are n + 1‐chromatic graphs. Wheter all graphs of chromatic number greater than n are persistent is a long‐standing open problem due to Hedetniemi. We call a graph G strongly persistent if G is persistent and the Hajos sum of G with any other persistent graph H is still persistent. This paper extends the class of known persistent graphs by proving the following results: If G is constructed from copies of K~n+1~ by Hajos sums, adding vertices and edges and at most one contraction of nonadjacent vertices, then G is strongly persistent. © 1929 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Lattices arising in categorial investiga
Lattices arising in categorial investigations of Hedetniemi's conjecture
✍ Dwight Duffus; Norbert Sauer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 844 KB

We discuss Hedetniemi's conjecture in the context of categories of relational structures under homomorphisms. In this language Hedetniemi's conjecture says that if there are no homomorphisms from the graphs G and H to the complete graph on n vertices then there is no homomorphism from G x H to the c