Odeljenje za matematiku, 28. jun 2012.

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


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ć.

Ostavite vaš komentar:

(nece biti prikazano)