Sabidussi versus Hedetniemi for three variations of the chromatic number

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10332614" target="_blank" >RIV/00216208:11320/16:10332614 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00493-014-3132-1" target="_blank" >http://dx.doi.org/10.1007/s00493-014-3132-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00493-014-3132-1" target="_blank" >10.1007/s00493-014-3132-1</a>

Result language
angličtina
Original language name
Sabidussi versus Hedetniemi for three variations of the chromatic number
Original language description
We investigate vector chromatic number ($chi_{vec}$), Lovasz V-function of the complement , and quantum chromatic number ($chi_{q}$ ) from the perspective of graph homomorphisms. We prove an analog of Sabidussi's theorem for each of these parameters, i.e., that for each of the parameters, the value on the Cartesian product of graphs is equal to the maximum of the values on the factors. Interestingly, as a consequence of this result for , we obtain analog of Hedetniemi's conjecture, i.e., that the value of on the categorical product of graphs is equal to the minimum of its values on the factors. We conjecture that the analogous results hold for vector and quantum chromatic number, and we prove that this is the case for some special classes of graphs.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)