Семинар за примењену математику, 21. децембар 2010.

Детаљније: Наредни састанак Семинара за примењену математику одржаће се у уторак, 21.12.2010. у 14:15, у сали 301ф МИ САНУ.

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

Назив предавања: A CLASS OF THREE COLORABLE TRIANGLE-FREE GRAPHS

Abstract: The chromatic number of a triangle-free graph can be arbitrarily large. In this talk we will show that if all subdivisions of $K_{2, 3}$ are also excluded as induced subgraphs, then the chromatic number is bounded by 3. We will give a structural characterization of this class of graphs, from which we derive an $O(nm)$ coloring algorithm.
Joint work with Kristina Vusković.


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

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


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

све вести