Сильна теорема про досконалі графи
твердження в теорії графів про те, що досконалі графи не мають ні непарних дір, ні непарних антидір / З Вікіпедії, безкоштовно encyclopedia
Сильна теорема про досконалі графи — це характеризація забороненими графами досконалих графів як точно тих графів, які не мають ні непарних дір (породжених циклів непарної довжини), ні непарних антидір (доповнень непарним дірам). Гіпотезу висловив Берж[en] 1961 року. Доведення Марії Чудновської, Нейла Робертсона[en], Пола Сеймура[en] та Робіна Томаса[en] заявлено 2002 року[1][2] та опубліковано 2006 року.
За доведення сильної теореми про досконалі графи автори отримали приз $10,000 від Джерарда Корніджолса з університету Карнегі-Меллон [1] та премію Фалкерсона 2009 [3] .