Sabidussi versus Hedetniemi for three variations of the chromatic number (Q1677539): Difference between revisions
From MaRDI portal
m rollbackEdits.php mass rollback Tag: Rollback |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2044987315 / rank | |||
Normal rank |
Revision as of 17:42, 21 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sabidussi versus Hedetniemi for three variations of the chromatic number |
scientific article |
Statements
Sabidussi versus Hedetniemi for three variations of the chromatic number (English)
0 references
10 November 2017
0 references
A well-known theorem of \textit{G. Sabidussi} [Monatsh. Math. 68, 426--438 (1964; Zbl 0136.44608)] states that the chromatic number of the Cartesian product of two graphs equals the maximum of the chromatic number of the factors. The authors show that an analog of the theorem of Sabidussi is true for vector chromatic number, strict vector chromatic number, and quantum chromatic number. A well-known conjecture of Hedetniemi claims that the chromatic number of the categorical product of two graphs equals the minimum of the chromatic number of the factors. It is shown in the paper that an analog of the conjecture is true for the strict vector chromatic number.
0 references
Cartesian product
0 references
categorical product
0 references
chromatic number
0 references
vector chromatic number
0 references
strict vector chromatic number
0 references
quantum chromatic number
0 references