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

DOI10.1016/J.JCTB.2019.02.008MaRDI QIDQ2338641zbMATH OpenOpenAlexWikidataFDO

Authors Marcin Wrochna

Publication date 21 November 2019

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

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

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)

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.

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

Cites work

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

Cited in

(12)

• In praise of homomorphisms
• Hedetniemi's conjecture and strongly multiplicative graphs
• 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

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)