Αντιπαράδειγμα στην εικασία Hedetniemi

[Mihalis_Lambrou]

Ο νεαρός Ρώσος μαθηματικός Yaroslav Shitov έλυσε με αντιπαράδειγμα την ετών εικασία Hedetniemi για τον χρωματισμό κάποιων γραφημάτων.

Βλέπε εδώ (αγγλιστί).

Η εικασία σχετίζεται με το Θεώρημα των χρωμάτων. Ρωτά αν ο χρωματικός αριθμός ενός γραφήματος της μορφής είναι ο ελάχιστος των χρωματικών αριθμών των . To αντιπαράδειγμα ονομάστηκε "διαμαντάκι" και έχει πολλές εφαρμογές σε πρακτικά προβλήματα.