On multiplicative graphs and the product conjecture
type: Item
instance of: scholarly article
title: On multiplicative graphs and the product conjecture
zbMATH Open document ID: 0657.05028
DOI: 10.1007/BF02122553
published in: Combinatorica
publication date: 1988-01-01T00:00:00Z
review text: A graph is called multiplicative if the class of all graphs not admitting a homomorphism into G is closed under taking the product of graphs. The authors study the multiplicativity of some families of graphs and their investigation is motivated by the product conjecture of Hedetniemi which asserts that all complete undirected graphs are multiplicative. One of the results of this paper provides the first non-trivial infinite family of multiplicative undirected graphs, namely the odd cycles. Another result, conjectured by Nešetřil and Pultr and proved by the authors is that the directed cycles of prime power length are also multiplicative. These two results, together with some simple remarks, give a complete characterization of all directed and undirected cycles which are multiplicative.
reviewed by: C.Radu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4072997
zbMATH Keywords: chromatic number
zbMATH Keywords: homomorphism of graphs
zbMATH Keywords: product of graphs
zbMATH Keywords: multiplicative undirected graphs
zbMATH Keywords: cycles
Wikidata QID: Q29545171
author: Roland Häggkvist
author: Pavol Hell
author: Donald J. Miller
author: V. Neumann-Lara
MaRDI profile type: Publication
cites work: On unavoidable digraphs in orientations of graphs
cites work: On the chromatic number of the product of graphs
cites work: The chromatic number of the product of two 4-chromatic graphs is 4
cites work: Homomorphisms of graphs into odd cycles
cites work: The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
cites work: On some strongly rigid families of graphs and the full embeddings they induce
cites work: Graphs and k-Societies
cites work: Cohomomorphisms of graphs and hypergraphs
cites work: The Categorical Product of Graphs
cites work: On classes of relations and graphs determined by subobjects and factorobjects
cites work: Fixed-edge theorem for graphs with loops
cites work: On the arc-chromatic number of a digraph
cites work: Symmetric graphs and interpretations
Recommended article: On the Hadwiger's conjecture for graph products
Recommended article: Partial product of graphs and Vizing's conjecture
Recommended article: Graph products and monochromatic multiplicities
Recommended article: Q3317148
Recommended article: The Conjugacy Problem for Finite Graph Products
Recommended article: The Farrell-Jones conjecture for graph products
Recommended article: Graph products and integer domination
Recommended article: Grundy number and products of graphs
Recommended article: Q3735737
Recommended article: Q4328255
description: scientific article; zbMATH DE number 4072997