Csúcsszínezést indukáló élsúlyozások

Témavezető: Madarasi Péter
ELTE TTK, Operációkutatási Tsz.
email: madarasip@staff.elte.hu

Projekt leírás

Az 1-2-3 sejtés [1] szerint minden legalább két élű, egyszerű, összefüggő gráf élei megsúlyozhatóak az 1,2,3 számokkal úgy, hogy a csúcsokra az oda illeszkedő élek súlyösszegét írva egy megengedett csúcsszínezést kapunk. A projekt célja a sejtés és néhány kapcsolódó kérdés vizsgálata.

Előfeltételek

A munkához szükséges programozói tapasztalat és az angol szakmai nyelv ismerete.

Hivatkozások

[1] Karoński, M., Łuczak, T., & Thomason, A. (2004). Edge weights and vertex colours. Journal of Combinatorial Theory Series B, 91(1), 151-157.

[2] Dudek, A., & Wajc, D. (2011) On the complexity of vertex-coloring edge-weightings. Discrete Mathematics and Theoretical Computer Science, 13(3), 45-50.

Korábbi hallgatók