Hedetniemi's Conjecture and Strongly Multiplicative Graphs
From MaRDI portal
Publication:5244123
DOI10.1137/19M1245013zbMath1427.05090arXiv1808.04778WikidataQ122933942 ScholiaQ122933942MaRDI QIDQ5244123
Publication date: 20 November 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.04778
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76)
Related Items (4)
Topology and Adjunction in Promise Constraint Satisfaction ⋮ Relatively small counterexamples to Hedetniemi's conjecture ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- A dichotomy theorem for circular colouring reconfiguration
- Square-free graphs are multiplicative
- Hedetniemi's conjecture and adjoint functors in thin categories
- Hom complexes and homotopy theory in the category of graphs
- Homotopy groups of Hom complexes of graphs
- Graph colorings, spaces of edges and spaces of circuits
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- On colorings of graph powers
- The chromatic number of the product of two 4-chromatic graphs is 4
- On multiplicative graphs and the product conjecture
- On classes of relations and graphs determined by subobjects and factorobjects
- On Hedetniemi's conjecture and the colour template scheme
- Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
- Hedetniemi's conjecture is asymptotically false
- Counterexamples to Hedetniemi's conjecture
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- Graph powers and graph homomorphisms
- Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- Homomorphism reconfiguration via homotopy
- Finding paths between 3-colorings
- Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings
- Fundamental groups of neighborhood complexes
- Graph homomorphism reconfiguration and frozen H‐colorings
- Hedetniemi's Conjecture and Strongly Multiplicative 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
This page was built for publication: Hedetniemi's Conjecture and Strongly Multiplicative Graphs
