Наредни састанак Семинара биће одржан у петак, 17. јануара 2024. године у сали 301ф Математичког института САНУ са почетком у 12.30 часова.
Предавач: Страхиња Гвоздић, ЕТХ Цирих
Наслов предавања: НАЈЛАКШЕ ЈЕ САВРШЕН ГРАФ ОБОЈИТИ
Апстракт: Граф G називамо савршеним уколико у сваком његовом индукованом подграфу H важи χ(H)=ω(H), где су са χ и ω означени, редом, хроматски број и највећа клика у N. Појам је први увео Берж 1961. када је и поставио две чувене хипотезе о структури савршених графова које су у међувремену доказане и данас су познате под називом слаба, односно јака, теорема о савршеним графовима. Прва хипотеза тврди да је комплемент сваког савршеног графа такође савршен, док друга даје потпуну структуралну карактеризацију савршених графова као графова који не садрже индуковане непарне циклусе дужине веће од 3 нити комплементе истих. На предавању ћемо дати доказ слабе теореме о савршеним графовима, представити главне идеје доказа јаке теореме о савршеним графовима и објаснити како се ефикасно (у полиномијалном времену) може израчунати хроматски број савршеног графа.
Напомена: Предавања се могу пратити на даљину преко линка:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Регистрациона форма је доступна на:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73