On inverse powers of graphs and topological implications of Hedetniemi's conjecture

DOI10.1016/J.JCTB.2019.02.008zbMATH Open1428.05259arXiv1712.03196OpenAlexW3106333994WikidataQ128137072 ScholiaQ128137072MaRDI QIDQ2338641FDOQ2338641

Authors: Marcin Wrochna 

Publication date: 21 November 2019

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

Abstract: We consider a natural graph operation $Omeg{a}_k$ that is a certain inverse (formally: the right adjoint) to taking the k-th power of a graph. We show that it preserves the topology (the $mathbb{Z}_2$-homotopy type) of the box complex, a basic tool in topological combinatorics. Moreover, we prove that the box complex of a graph G admits a $mathbb{Z}_2$-map (an equivariant, continuous map) to the box complex of a graph H if and only if the graph $Omeg{a}_k(G)$ admits a homomorphism to H, for high enough k. This allows to show that if Hedetniemi's conjecture on the chromatic number of graph products were true for n-colorings, then the following analogous conjecture in topology would also also true: If X,Y are $mathbb{Z}_2$-spaces (finite $mathbb{Z}_2$-simplicial complexes) such that X x Y admits a $mathbb{Z}_2$-map to the (n-2)-dimensional sphere, then X or Y itself admits such a map. We discuss this and other implications, arguing the importance of the topological conjecture.

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

Recommendations

• Hedetniemi's conjecture from the topological viewpoint
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• A survey on Hedetniemi's conjecture
• Applications of Hajós-type constructions to the Hedetniemi conjecture
• An approach to hedetniemi's conjecture

zbMATH Keywords

indexadjoint functorhomomorphismbox complexHedetniemi's conjectureodd girth

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Graph theory (05C99)

Cites Work

• Morse theory for cell complexes
• Graph powers and graph homomorphisms
• The right adjoints into the categories of relational systems
• On the complexity of H-coloring
• On theorems of Borsuk-Ulam, Kakutani-Yamabe-Yujobô and Dyson. I
• Combinatorial algebraic topology
• Kneser's conjecture, chromatic number, and homotopy
• On multiplicative graphs and the product conjecture
• A survey on Hedetniemi's conjecture
• On colorings of graph powers
• Local chromatic number and distinguishing the strength of topological obstructions
• Local chromatic number, Ky Fan's theorem, and circular colorings
• 4-chromatic projective graphs
• Fixed point free involutions and equivariant maps
• 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
• The chromatic number of the product of two 4-chromatic graphs is 4
• A user's guide to discrete Morse theory
• Topology of Hom complexes and test graphs for bounding chromatic number
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Square-free graphs are multiplicative
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Hedetniemi's conjecture---a survey
• On topological relaxations of chromatic conjectures
• Title not available (Why is that?)
• Levels in algebra and topology
• On the arc-chromatic number of a digraph
• Uniform versions of index for uniform spaces with free involutions
• On theorems of Borsuk-Ulam, Kakutani-Yamabe-Yujobô and Dyson. II
• Title not available (Why is that?)
• Fixed Point Free Involutions and Equivariant Maps. II
• On graphs with strongly independent color-classes
• ON THE INDEX AND CO-INDEX OF SPHERE BUNDLES
• Digraph functors which admit both left and right adjoints
• Iterated arc graphs.
• Levels in algebra and topology
• Homotopy types of box complexes
• The level of real projective spaces
• Hedetniemi's conjecture and adjoint functors in thin categories
• Universality of \(A\)-mote graphs
• Colouring quadrangulations of projective spaces
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• The level of nonmultiplicativity of graphs
• A Note on Fixed Point Free Involutions and Equivariant Maps
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• Some examples of non-tidy spaces

Cited In (12)

• In praise of homomorphisms
• Counterexamples to Hedetniemi's conjecture
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• On a problem of Domke, Dunbar, Haynes, Hedetniemi, and Markus concerning the inverse domination number
• Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
• Topology and Adjunction in Promise Constraint Satisfaction
• Shannon capacity and the categorical product
• On multichromatic numbers of widely colorable graphs
• Dominance complexes, neighborhood complexes and combinatorial Alexander duals
• Hedetniemi's conjecture from the topological viewpoint
• The chromatic number of the product of 14-chromatic graphs can be 13
• Hedetniemi's conjecture and strongly multiplicative graphs

This page was built for publication: On inverse powers of graphs and topological implications of Hedetniemi's conjecture

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