Square-free graphs are multiplicative

DOI10.1016/J.JCTB.2016.07.007zbMATH Open1350.05074arXiv1601.04551OpenAlexW3102760800MaRDI QIDQ345100FDOQ345100

Authors: Marcin Wrochna 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A graph K is square-free if it contains no four-cycle as a subgraph. A graph K is multiplicative if GxH -> K implies G -> K or H -> K, for all graphs G,H. Here GxH is the tensor (or categorical) graph product and G -> K denotes the existence of a graph homomorphism from G to K. Hedetniemi's conjecture states that all cliques K_n are multiplicative. However, the only non-trivial graphs known to be multiplicative are K_3, odd cycles, and still more generally, circular cliques $K_{p/q}$ with 2 <= p/q < 4. We make no progress for cliques, but show that all square-free graphs are multiplicative. In particular, this gives the first multiplicative graphs of chromatic number higher than 4. Generalizing, in terms of the box complex, the topological insight behind existing proofs for odd cycles, we also give a different proof for circular cliques.

Full work available at URL: https://arxiv.org/abs/1601.04551

Recommendations

• Hedetniemi's conjecture and strongly multiplicative graphs
• On multiplicative graphs and the product conjecture
• Counterexamples to Hedetniemi's conjecture
• On the chromatic number of the product of graphs
• A survey on Hedetniemi's conjecture

zbMATH Keywords

homotopyhomomorphismbox complexfour-cycle-free graphHedetniemi's conjecturemultiplicativitysquare-free graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• On multiplicative graphs and the product conjecture
• A survey on Hedetniemi's conjecture
• Hom complexes and homotopy theory in the category of graphs
• The complexity of change
• Finding paths between 3-colorings
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Homomorphism reconfiguration via homotopy
• A dichotomy theorem for circular colouring reconfiguration
• Circular chromatic number: A survey
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Homotopy type of the box complexes of graphs without 4-cycles
• The chromatic number of the product of two 4-chromatic graphs is 4
• Homomorphisms of products of graphs into graphs without four cycles
• On Hedetniemi's conjecture and the colour template scheme
• Lattices arising in categorial investigations of Hedetniemi's conjecture
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Title not available (Why is that?)
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hedetniemi's conjecture---a survey
• On topological relaxations of chromatic conjectures

Cited In (8)

• Reconfiguring graph homomorphisms on the sphere
• Hedetniemi's conjecture and adjoint functors in thin categories
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Topology and Adjunction in Promise Constraint Satisfaction
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Relatively small counterexamples to Hedetniemi's conjecture
• On a class of square-free graphs
• Hedetniemi's conjecture and strongly multiplicative graphs

This page was built for publication: Square-free graphs are multiplicative

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345100)