Sabidussi versus Hedetniemi for three variations of the chromatic number

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Sabidussi versus Hedetniemi for three variations of the chromatic number

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Sabidussi versus Hedetniemi for three variations of the chromatic number

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Combinatorica

ISSN

0209-9683

e-ISSN

—

Svazek periodika

36

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

21

Strana od-do

395-415

Kód UT WoS článku

000382389800002

EID výsledku v databázi Scopus

2-s2.0-84922379033