Η Εικασία Erdős–Faber–Lovász – Ένα Πρόβλημα Χρωματισμού Γράφων

Η Εικασία Erdős–Faber–Lovász είναι ένα από τα πιο διάσημα προβλήματα της σύγχρονης συνδυαστικής θεωρίας γράφων. Διατυπώθηκε το 1972 από τους Paul Erdős, Vance Faber και László Lovász και παρέμεινε ανοιχτή για σχεδόν πέντε δεκαετίες.

---

🔵 Το Πρόβλημα

Έστω ότι έχουμε $k$ κλίκες (πλήρη γραφήματα), καθεμία με $k$ κορυφές.

Υποθέτουμε ότι:

• Κάθε ζεύγος κλικών τέμνεται το πολύ σε μία κορυφή.

• Δεν υπάρχουν άλλες κοινές κορυφές πέρα από αυτές τις μοναδικές τομές.

Το ερώτημα είναι:

Μπορεί το σύνολο των κορυφών να χρωματιστεί πάντα με ακριβώς $k$ χρώματα, έτσι ώστε καμία ακμή να μην συνδέει κορυφές ίδιου χρώματος;

Με άλλα λόγια:
Είναι ο χρωματικός αριθμός τέτοιου γράφου το πολύ $k$;

---

🟣 Τι δείχνει το σχήμα;

Στην εικόνα παρουσιάζεται η περίπτωση $k = 4$:

• Τέσσερις κλίκες τεσσάρων κορυφών.

• Κάθε δύο κλίκες τέμνονται σε ακριβώς μία κορυφή.

• Τέσσερα χρώματα αρκούν για σωστό χρωματισμό.

Το ερώτημα είναι αν αυτό ισχύει για κάθε k.

---

🟢 Η Μεγάλη Εξέλιξη (2021)

Το 2021, οι Dong Yeap Kang, Daniela Kühn, Abhishek Methuku και Deryk Osthus απέδειξαν ότι η εικασία είναι αληθής για αρκετά μεγάλο $k$.

Λίγο αργότερα δόθηκε πλήρης απόδειξη για κάθε $k$, κλείνοντας οριστικά το πρόβλημα.

---

🔴 Γιατί Είναι Σημαντική;

Η εικασία:

• Συνδέει τη θεωρία γράφων με υπεργράφους.

• Σχετίζεται με προβλήματα χρωματισμού και συνδυαστική δομή τομών.

• Αποτελεί χαρακτηριστικό παράδειγμα προβλήματος που φαίνεται «απλό», αλλά απαιτεί βαθιά θεωρητικά εργαλεία.