Sabidussi versus Hedetniemi for three variations of the chromatic number

DOI10.1007/s00493-014-3132-1zbMath1389.05040arXiv1305.5545OpenAlexW2044987315MaRDI QIDQ1677539

Robert Šámal, David E. Roberson, Simone Severini, Chris D. Godsil

Publication date: 10 November 2017

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberCartesian productquantum chromatic numbercategorical productstrict vector chromatic numbervector chromatic number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items (10)

Shannon capacity and the categorical product ⋮ Universal completability, least eigenvalue frameworks, and vector colorings ⋮ A Sum of Squares Characterization of Perfect Graphs ⋮ Graph homomorphisms via vector colorings ⋮ Vector coloring the categorical product of graphs ⋮ Altermatic number of categorical product of graphs ⋮ Quantum multiplicative graph and a type of separate clique number ⋮ Chromatic numbers, Sabidussi's theorem and Hedetniemi's conjecture for non-commutative graphs ⋮ More tales of Hoffman: bounds for the vector chromatic number of a graph ⋮ Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Cites Work

• The fractional version of Hedetniemi's conjecture is true
• On the quantum chromatic number of a graph
• Equiarboreal graphs
• The sandwich theorem
• Vertex-transitive graphs
• New Separations in Zero-Error Channel Capacity Through Projective Kochen–Specker Sets and Quantum Coloring
• Forbidden Intersections
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sabidussi versus Hedetniemi for three variations of the chromatic number