On multiplicative graphs and the product conjecture

DOI10.1007/BF02122553zbMath0657.05028WikidataQ29545171 ScholiaQ29545171MaRDI QIDQ1110530

Víctor Neumann-Lara, Pavol Hell, Donald J. Miller, Roland Haeggkvist

Publication date: 1988

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

cycleschromatic numberproduct of graphshomomorphism of graphsmultiplicative undirected graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Homomorphisms to oriented paths ⋮ Minimum cost homomorphism dichotomy for oriented cycles ⋮ On the complexity of H-coloring ⋮ Compactness and finite equivalence of infinite digraphs ⋮ The complexity of restricted graph homomorphisms ⋮ On multiplicative graphs and the product conjecture ⋮ Square-free graphs are multiplicative ⋮ Lattices arising in categorial investigations of Hedetniemi's conjecture ⋮ Star-extremal graphs and the lexicographic product ⋮ Multiplicativity of acyclic digraphs ⋮ Coloring graph products---a survey ⋮ Complexity of tree homomorphisms ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Semidefinite programming and its applications to NP problems ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ The effect of two cycles on the complexity of colourings by directed graphs ⋮ Foldings in graphs and relations with simplicial complexes and posets ⋮ Relatively small counterexamples to Hedetniemi's conjecture ⋮ Path homomorphisms ⋮ A simple proof of the multiplicativity of directed cycles of prime power length ⋮ Hedetniemi's conjecture and adjoint functors in thin categories ⋮ Multiplicative posets ⋮ On the complexity of colouring by superdigraphs of bipartite graphs ⋮ Achromatic numbers and graph operations ⋮ Learning logic programs with structured background knowledge ⋮ Counterexamples to Hedetniemi's conjecture ⋮ Duality pairs and homomorphisms to oriented and unoriented cycles ⋮ Note on Hedetniemi's conjecture and the Poljak-Rödl function ⋮ CSP dichotomy for special triads ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Hereditarily hard \(H\)-colouring problems ⋮ Chromatic Ramsey numbers ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ Multiplicative graphs and semi-lattice endomorphisms in the category of graphs ⋮ On inverse powers of graphs and topological implications of Hedetniemi's conjecture

Cites Work

• Symmetric graphs and interpretations
• The chromatic number of the product of two 4-chromatic graphs is 4
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• On multiplicative graphs and the product conjecture
• On the arc-chromatic number of a digraph
• On some strongly rigid families of graphs and the full embeddings they induce
• On classes of relations and graphs determined by subobjects and factorobjects
• Homomorphisms of graphs into odd cycles
• On unavoidable digraphs in orientations of graphs
• On the chromatic number of the product of graphs
• Fixed-edge theorem for graphs with loops
• Cohomomorphisms of graphs and hypergraphs
• The Categorical Product of Graphs
• Graphs and k-Societies