Graf teorisinin en zorlu problemlerinden biri olan ve 1985 yılından bu yana matematik camiasını meşgul eden bir soru nihayet yanıt buldu. Macar matematikçi Gyárfás tarafından ortaya atılan bu problem, grafik renklendirme teorisinin temel taşlarından biriydi.
Araştırmacılar, beş köşeli yol yapısı (P₅) içermeyen grafiklerde kromatik sayının klik sayısıyla polinomsal bir ilişki içinde olduğunu kanıtlamayı başardı. Kromatik sayı, bir grafikteki komşu olmayan köşelerin aynı renge boyanabilmesi için gereken minimum renk sayısını ifade ederken, klik sayısı ise birbirine tamamen bağlı olan en büyük köşe grubunun boyutunu gösterir.
Çözümün anahtarı, araştırmacıların geliştirdiği yenilikçi 'kromatik yoğunluk çerçevesi' oldu. Bu yaklaşım, kromatik yarı-rastgelelik ve kromatik yoğunluk artımı kavramlarını bir araya getirerek, daha önce Erdős-Hajnal tarafından P₅ için elde edilen sonuçlardan yararlanmayı mümkün kıldı.
Bu başarı, sadece teorik matematik açısından değil, pratik uygulamalar açısından da büyük önem taşıyor. Graf renklendirme problemleri, ağ tasarımından kaynak dağıtımına, zamanlama problemlerinden harita boyama algoritmalarına kadar pek çok alanda kullanılıyor. 40 yıllık bu problemin çözülmesi, kombinatorik ve bilgisayar bilimi alanlarında yeni araştırma yolları açacak.