Семинар за примењену математику, 21. децембар 2010.
- 20. Децембар, 2010
- Коментари (0)
Детаљније: Наредни састанак Семинара за примењену математику одржаће се у уторак, 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ć.
Коментари(0)