A SURVEY ON HEDETNIEMI'S CONJECTURE

1998/03/01 by Xuding Zhu · 1 citation
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Conjecture #Mathematics #Categorical variable #Product (mathematics) #Combinatorics #Point (geometry) #Chromatic scale #Pure mathematics #Statistics #Geometry

paper · pdf · doi:10.11650/twjm/1500406890

openalex publication_date 1998/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

More than 30 years ago, Hedetniemi made a conjecture which says that the categorical product of two n-chromatic graphs is still n-chromatic. The conjecture is still open, despite many dierent approaches from dierent point of views. This article surveys methods and partial results; and discuss problems related to or motivated by this conjecture.

Citations

• Graph homomorphisms: structure and symmetry
• Lattices arising in categorial investigations of Hedetniemi's conjecture
• Coloring graph products — A survey
• The chromatic number of the product of two ℵ1-chromatic graphs can be countable
• On multiplicative graphs and the product conjecture
• On the arc-chromatic number of a digraph
• Color-families are dense
• The chromatic number of the product of two 4-chromatic graphs is 4
• On the chromatic number of the product of graphs

Cited by

• Hedetniemi's conjecture [wikipedia]