On Hedetniemi's conjecture and the colour template scheme (Q1613520)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On Hedetniemi's conjecture and the colour template scheme
scientific article

    Statements

    On Hedetniemi's conjecture and the colour template scheme (English)
    0 references
    0 references
    0 references
    29 August 2002
    0 references
    Hedetniemi's conjecture states that the chromatic number of a product of graphs is the minimum of the chromatic numbers of the factors. It is shown that if \(G\) and \(H\) are connected graphs of chromatic number at least 5 and both contain odd wheels as subgraphs, then their product also has chromatic number at least 5. The paper also provides counterexamples to the conjecture of El-Zahar and Saucer on the structure of \(n\)-chromatic subgraphs of products of \(n\)-chromatic graphs, implying that their method is not sufficient to prove all cases of Hedetniemi's conjecture for chromatic number larger than 4.
    0 references
    0 references
    homomorphism
    0 references
    chromatic number of a product of graphs
    0 references

    Identifiers