Square-free graphs are multiplicative

DOI10.1016/J.JCTB.2016.07.007MaRDI QIDQ345100zbMATH OpenOpenAlexFDO

Authors Marcin Wrochna

Publication date 25 November 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5130830 (Why is no real title available?)
• scientific article; zbMATH DE number 3811849 (Why is no real title available?)
• scientific article; zbMATH DE number 3728320 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A dichotomy theorem for circular colouring reconfiguration
• A survey on Hedetniemi's conjecture
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Circular chromatic number: A survey
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Hedetniemi's conjecture---a survey
• Hom complexes and homotopy theory in the category of graphs
• Homomorphism reconfiguration via homotopy
• Homomorphisms of products of graphs into graphs without four cycles
• Homotopy type of the box complexes of graphs without 4-cycles
• Kneser's conjecture, chromatic number, and homotopy
• Lattices arising in categorial investigations of Hedetniemi's conjecture
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• On Hedetniemi's conjecture and the colour template scheme
• On multiplicative graphs and the product conjecture
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• On topological relaxations of chromatic conjectures
• The chromatic number of the product of two 4-chromatic graphs is 4
• The complexity of change
• 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

Cited in

(8)

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