Одељење за математику, 16. март 2018.

Наредни састанак Семинара биће одржан у петак, 16. марта 2018. у сали 301ф Математичког института САНУ са почетком у 14:15 часова.

Предавач: Бојан Вучковић, Математички факултет, Универзитет у Београду

Наслов предавања: ИНДУКОВАНА БОЈЕЊА ГРАФОВА

Апстракт: Бојење графа подразумева доделу боја чворовима, гранама, или чворовима и гранама графа. Уобичајени услов код ових бојења је да се суседним чворовима, инцидентним гранама, односно чворовима и њима инцидентним гранама, додељују различите боје. Оваква бојења називају се ваљаним, и највише изучавани проблем је који је минималан броја боја потребних да би се такво бојење извело. Поред ваљаних бојења, последњих деценија постоји значајно интересовање за индукована бојења графова. То су не обавезно ваљана бојења код којих се боја чвора изводи из боја њему инцидентних грана. Бојења се најчешће изводе по суми или по скупу, при чему се поставља услов да свака два суседна чвора, или генерално свака два чвора графа, имају различите изведене вредности. На излагању ће бити приказане дефиниције разних врста индукованог бојења графа, као и хипотезе по питању потребног броја боја да би се извело тражено бојење за произвољан граф. Код многих од ових типова бојења постигнути резултати су још увек далеко од претпостављених горњих граница датих у хипотезама и остављају простора за даље унапређивање.


Нажалост није могуће оставити коментар.

Вести и дешавања


Активности на семинарима

све вести