Одељење за математику, 28. јун 2012.

• 25. Јун, 2012
• Коментари (0)

Наредни састанак Одељења за математику биће одржан у четвртак, 28. јуна 2012. године у сали 301ф, са почетком у 13h.

Предавач: Maria Chudnovsky, Department of Industrial Engineering and Operations Research Department of Mathematics, Columbia University

Наслов предавања: COLORING SOME PERFECT GRAPHS

Садржај: 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ć.