Prednáška

Abstrakt

Jedným z ústredných problémov teórie grafov je problém vrcholového farbenia. Veľmi veľa problémov farbenia sa dá formulovať jednoduchým spôsobom, ale ich riešenie je často prekvapujúce a zložité. Na druhej strane farbenie grafov má veľmi veľa aplikácií pri riešení praktických úloh. Vlastnosťou grafov sa nazýva trieda grafov, ktorá je uzavretá vzhľadom na izomorfizmus. Vlastnosť sa nazýva dedičná (indukovane dedičná), ak je uzavretá na tvorenie podgrafov (indukovaných podgrafov). Vlastnosť sa nazýva aditívna ak je uzavretá vzhľadom na disjunktné zjednotenie grafov. Jazyk dedičných vlastností grafov umožňuje systémový pohľad na problematiku zovšeobecneného farbenia grafov. Umožňuje skúmať štrukturálne vlastnosti individuálnych grafových vlastností, ale aj systému grafových vlastností. V našom príspevku predstavíme

• základné vlastnosti zväzu dediených vlastností grafov
• charakterizáciu dedičných vlastností grafov pomocou zakázaných podštruktúr
• vybrané extremálne problémy
• grafové invarianty a ich vzťah k reťazcom dedičných vlastností
• minimálne reducibilné ohraničenia a ich využitie pri porovnávaní kvality dosiahnutých výsledkov
• jednoznačný rozklad dedičných vlastností na ireducibilné faktory
• výpočtovú zložitosť vybraných súvisiacich problémov
• aplikáciu formálnej konceptovej analýzy

Videozáznam z prednášky