Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak‐Rödl function

2005/08/05 by Claude Tardif, David L. Wehlau · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Mathematics #Bounded function #Graph #Undirected graph #Discrete mathematics #Function (biology)

paper · doi:10.1002/jgt.20117

openalex publication_date 2005/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

Abstract Let f ( n ) = minχ( G × H ) : G and H are n ‐chromatic digraphs and g ( n ) = minχ( G × H ) : G and H are n ‐chromatic graphs. We prove that f is bounded if and only if g is bounded. © 2005 Wiley Periodicals, Inc. J Graph Theory

Citations

• On multiplicative graphs and the product conjecture
• The chromatic number of the product of two 4-chromatic graphs is 4

Cited by

• Hedetniemi's conjecture [wikipedia]