Odeljenje za matematiku, 28. jun 2012.
- 25. Jun, 2012
- Komentari (0)
Naredni sastanak Odeljenja za matematiku biće održan u četvrtak, 28. juna 2012. godine u sali 301f, sa početkom u 13h.
Predavač: Maria Chudnovsky, Department of Industrial Engineering and Operations Research Department of Mathematics, Columbia University
Naslov predavanja: COLORING SOME PERFECT GRAPHS
Sadržaj: A graph G is called perfect if for every induced subgraph H of G, the chromatic number and the clique number of H are equal. After the recent proof of the Strong Perfect Graph Theorem, and the discovery of a polynomial-time recognition algorithm, the central remaining open question about perfect graphs is finding a combinatorial polynomial-time coloring algorithm. (There is a polynomial-time algorithm known, using the ellipsoid method). Recently, we were able to find such an algorithm for a certain class of perfect graphs, that includes all perfect graphs admitting no balanced skew-partition. The algorithm is based on finding special "extremal" decompositions in such graphs; we also use the idea of "trigraphs".
This is joint work with Nicolas Trotignon, Theophile Trunck and Kristina Vušković.