Семинар Катедре за рачунарство и информатику, 8. март 2018.

• 06. Март, 2018
• Коментари (0)

Наредни састанак Семинара биће одржан у четвртак, 8. марта 2018. у сали 718 Математичког факултета са почетком у 18:15 часова.

Предавач: Бојан Вучковић

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

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

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

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