• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 20 публикаций
Сортировка:
по названию
по году
Статья
Bigeni A. Discrete Mathematics. 2015. Vol. 338. No. 8. P. 1432-1448.
Добавлено: 7 ноября 2016
Статья
Beaudou L., Devroye L., Hahn G. Discrete Mathematics. 2019. Vol. 342. No. 1. P. 143-144.
Добавлено: 11 февраля 2019
Статья
Cherkashin Danila. Discrete Mathematics. 2018. Vol. 341. No. 3. P. 652-657.
Добавлено: 30 января 2018
Статья
Shabanov D. A. Discrete Mathematics. 2015. Vol. 338. No. 11. P. 1976-1981.
Добавлено: 6 октября 2015
Статья
Dagaev D., Schurov I. Discrete Mathematics. 2020. Vol. 343. No. 4. P. 111704.
Добавлено: 15 октября 2019
Статья
Shabanov D. A., Akhmejanova M. Discrete Mathematics. 2020. Vol. 343. No. 4. P. 1-11.
Добавлено: 31 октября 2019
Статья
Shabanov D. A., Akolzin I. A. Discrete Mathematics. 2016. Vol. 339. No. 12. P. 3020-3031.
Добавлено: 4 сентября 2016
Статья
Gurvich V., Gol'berg A., Andrade D. V. et al. Discrete Mathematics. 2014. Vol. 329. P. 19-32.
Добавлено: 22 октября 2016
Статья
Omelchenko A., Краско Е. С. Discrete Mathematics. 2019. Vol. 342. No. 2. P. 600-614.
Добавлено: 21 сентября 2018
Статья
Omelchenko A., Краско Е. С. Discrete Mathematics. 2019. Vol. 342. No. 2. P. 584-599.
Добавлено: 21 сентября 2018
Статья
Bogdanov I. I., Chelnokov G. R. Discrete Mathematics. 2013. Vol. 313. No. 5. P. 622-625.
Добавлено: 9 марта 2018
Статья
Beaudou L., Naserasr R., Tardif C. Discrete Mathematics. 2015. Vol. 338. No. 12. P. 2539-2544.
Добавлено: 11 апреля 2019
Статья
Atminas A., Collins A., Lozin V. et al. Discrete Mathematics. 2015. Vol. 338. No. 2. P. 164-179.
Добавлено: 16 марта 2015
Статья
Jerónimo-Castro J., Magazinov A., Soberón P. Discrete Mathematics. 2015. Vol. 338. No. 9. P. 1577-1585.
Добавлено: 4 октября 2018
Статья
Gurvich V., Boros E., Milanic M. Discrete Mathematics. 2014. Vol. 318. P. 78-95.
Добавлено: 22 октября 2016
Статья
Lozin V. V., Dabrowski K., Zamaraev V. A. Discrete Mathematics. 2012. Vol. 312. No. 16. P. 2457-2465.

Для класса графов X через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. В качестве одного из подходов к исследованию факториальных классов, в данной работе рассматриваются минимальные сверхфакториальные классы. В [J.P. Spinrad, Nonredundant 1's in Γ-free matrices, SIAM Journal on Discrete Mathematics,  8 (1995) 251--257], Спинрад показал, что число n-вершинных хордальных двудольных графов равно 2Θ(n log2n), то есть данный класс – сверхфакториальный. С другой стороны, все известные из литературы наследственные подклассы класса хордальных двудольных графов являются факториальными. Помимо лесов, к ним, в частности, относятся двудольные перестановочные графы, двудольные вполне сепарабельные графы, выпуклые графы. В данной работе изучаются новые наследственные подклассы класса хордальных двудольных графов и среди них выявляются как факториальные, так и сверхфакториальные. Последний результат показывает, что класс хордальных двудольных графов не является минимальным сверхфакториальным. Поиск минимальных сверхфакториальных подклассов класса хордальных двудольных графов остается открытым вопросом.

Добавлено: 28 июня 2012
Статья
Gurvich V., Boros E. Discrete Mathematics. 2015. Vol. 338. No. 12. P. 2421-2436.
Добавлено: 22 октября 2016
Статья
Boros E., Cepek O., Gurvich V. Discrete Mathematics. 2019. Vol. 342. No. 5. P. 1275-1292.
Добавлено: 18 марта 2019
Статья
Talambutsa A., Kolpakov A. Discrete Mathematics. 2020. Vol. 343. No. 3.
Добавлено: 15 марта 2020
Статья
Malyshev D. Discrete Mathematics. 2015. Vol. 338. No. 11. P. 1860-1865.

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. © 2015 Elsevier B.V. All rights reserved.

Добавлено: 7 апреля 2014