Семинар за рачунарство и примењену математику, 23. децембар 2015.

• 21. Децембар, 2015
• Коментари (0)

Наредни састанак Семинара биће одржан у среду, 23. децембра 2015. у сали 301ф Математичког института САНУ са почетком у 14:15 часова.

Предавач: Кристина Вушковић, Рачунарски факултет Универзитет УНИОН, School of Computing, Faculty of Engineering, University of Leeds

Наслов предавања: COLORING SQUARE-FREE PERFECT GRAPHS

Апстракт: A graph is perfect if for all of its induced subgraphs, the chromatic number equals to the size of its largest clique. These graphs were introduced by Berge in 1961, who was motivated by the study of communication theory. They inspired an enormous amount of research from different fields.
In 2002 the famous Strong Perfect Graph Conjecture (that characterizes perfect graphs in terms of excluded induced subgraphs) was proved by Chudnovsky, Robertson, Seymour and Thomas. In 2003 it was shown by Chudnovsky, Cornuéjols, Liu, Seymour and Vuškovićthat the class can be recognized in polynomial time. In 1981 Grötschel, Lovász and Schrijver showed that perfect graphs can be optimally colored in polynomial time, using the ellipsoid method. The last big open problem in the area is to find a purely 'combinatorial” polynomial time coloring algorithm for perfect graphs.In this talk we present such an algorithm for the class of perfect graphs that do not contain as induced subgraph a chordless cycles of length 4 (square-free perfect graphs). This is joint work with Chudnovsky, Lo, Maffray and Trotignon.