Семинар за рачунарство и примењену математику, 24. април 2012.

• 23. Април, 2012
• Коментари (0)

Наредни састанак Семинара за рачунарство и примењену математику одржаће се у уторак, 24. априла 2012. у 14:15, соба 301ф МИ САНУ.

Предавач: Alain Hertz, GERAD - Ecole des HEC & Ecole Polytechnique, Montreal, Canada

Наслов предавања: ON THE MAXIMUM DIFFERENCE BETWEEN SEVERAL GRAPH INVARIANTS

Abstract: A graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph. Although bounds on invariants have been studied for a long time by graph theorists, the past few years have seen a surge of interest in the systematic study of linear relations (or other kinds of relations) between graph invariants. We focus our attention on the difference between the maximum orders of an induced (linear) forest, an induced tree, an induced bipartite graph, and a stable set. We give upper bounds on these differences, and prove that there are tight.