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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references