Seminar za primenjenu matematiku, 21. decembar 2010.

• 20. Decembar,  2010
• Komentari (0)

Detaljnije: Naredni sastanak Seminara za primenjenu matematiku održaće se u utorak, 21.12.2010. u 14:15, u sali 301f MI SANU.

Predavač: Marko Radovanović, Računarski fakultet, Univerzitet Union, Beograd

Naziv predavanja: 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ć.

---