Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Название статьи

НЕКОТОРЫЕ РЕЗУЛЬТАТЫ О НАСЛЕДСТВЕННЫХ КЛАССАХ ГРАФОВ. III

Номер журнала	6
Дата выпуска	2013

Тип статьи	научная статья	Коды УДК	519.17
Страницы	165-172	Ключевые слова	наследственный класс графов, запрещенный порожденный подграф, фильтрованный класс графов, вычислительная сложность, эффективный алгоритм, упаковки графов, покрытия графов

Авторы

Алексеев В.Е.Замараев В.А.Захарова Д.В.Малышев Д.С.Мокеев Д.Б.Сорочан С.В.

Место работы

Алексеев В.Е. Нижегородский госуниверситет им. Н.И. Лобачевского
Замараев В.А. Нижегородский филиал Национального исследовательского университета «Высшая школа экономики»
Захарова Д.В. Нижегородский госуниверситет им. Н.И. Лобачевского
Малышев Д.С. Нижегородский филиал Национального исследовательского университета «Высшая школа экономики»
Мокеев Д.Б. Нижегородский филиал Национального исследовательского университета «Высшая школа экономики»
Сорочан С.В. Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурногоописания, исследуется сложность некоторых задач на таких классах.

Загрузить статью

Библиографический список

1 . Алексеев В.Е. О влиянии локальных ограничений на сложность определения числа независимости графа // В сб.: Комбинаторно-алгебраические методы в прикладной математике / Под ред. А.А. Маркова. Горький: Изд-во ГГУ. 1982. С. 3–13.
2 . Alekseev V.E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. 2004. V. 132. P. 17–26.
3 . Алексеев В.Е., Захарова Д.В., Малышев Д.С. и др. Некоторые результаты о наследственных классах графов II // Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. Вып. 6(1). С. 115–120.
4 . Алексеев В.Е. Верхняя оценка числа максимальных независимых множеств графа // Дискретная математика. 2007. Т. 19. № 3. С. 84–88.
5 . Tsukigama S., Ide M., Ariochi H., Ozaki H. A new algorithm for generating all the maximal inde-pendence sets // SIAM J. Comput. 1977. V. 6. P. 505–517.
6 . Natanzon A., Shamir R., Sharan R. Complexity classification of some edge modification problems // Discrete Appl. Math. 2001. V. 113. P. 109–118.
7 . Hakimi S.L., Brederson J.G. Graph-theoretic error-correcting codes // IEEE Trans. Inform. Theory. 1968. V. 14. P. 584–591.
8 . Захарова Д.В. Симметрические линейные пространства графов // Дискретная математика. 2011. Т. 23. № 2. С. 103–107.
9 . Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144. P. 173–182.
10 . Малышев Д.С. О количестве граничных классов в задаче о 3-раскраске // Дискретная математика. 2009. Т. 21. № 4. С. 129–134.
11 . Малышев Д.С. О бесконечности множества граничных классов в задаче о реберной 3-раскраске // Дискретный анализ и исследование операций. 2009. Т. 16. № 1. С. 37–43.
12 . Малышев Д.С. Континуальные множества граничных классов графов для задач о раскраске // Дискретный анализ и исследование операций. 2009. Т. 16. № 5. С. 41–51.
13 . Korpelainen N., Lozin V.V., Malyshev D., Tiskin A. Boundary properties of graphs for algorithmic graph problems // Theoretical Computer Science. 2011. V. 412. P. 3545–3554.
14 . Малышев Д.С. О пересечении и симметрической разности семейств граничных классов для задач о раскраске и о хроматическом числе // Дискретная математика. 2012. Т. 24. № 2. С. 75–78.
15 . Kral D., Kratochvil J., Tuza Z., Woeginger G.J. Complexity of coloring graphs without forbidden induced subgraphs // Lecture Notes in Computer Sci-ence. 2001. V. 2204. P. 254–262.
16 . Lozin V.V., Malyshev D.S. Vertex coloring of graphs with few obstructions // Theoretical Computer Science (submitted).
17 . Robertson N., Seymour P.D. Graph Minors. XX. Wagner’s conjecture // J. Combin. Theory. Ser. B. 2004. V. 92. P. 325–357.
18 . Damaschke P. Induced subgraphs and well-quasi-ordering // J. Graph Theory. 1990. V. 14. P. 427–435.
19 . Lozin V.V., Mayhill C., Zamaraev V. Locally bounded coverings and factorial properties of graphs // European Journal of Combinatorics. 2012. V. 33(4). P. 534–543.
20 . Norine S., Seymour P., Thomas R., Wollan P. Proper minor-closed families are small // J. Combin. Theory. Ser. B. 2006. V. 96. P. 754–757.
21 . Ding G. Subgraphs and Well-Quasi-Ordering // J. Graph Theory. 1992. V. 16. P. 489–502.
22 . Алексеев В.Е. О нижних ярусах решётки на-следственных классов графов // Дискрет. анализ и исслед. операций. 1997. Т. 4. № 1. С. 3–12.
23 . Алексеев В.Е. Область значений энтропии наследственных классов графов // Дискретная математика. 1992. Т. 4. № 2. С. 148–157.
24 . Алексеев В.Е., Сорочан С.В. Об энтропии наследственных классов цветных графов // Дискретная математика. 2000. Т. 12. № 2. С. 99–102.
25 . Сорочан С.В. Об энтропии композиций наследственных классов цветных графов // Дискретный анализ и исследование операций. Сер. 1. 2002. Т. 9. № 1. С. 59–83.
26 . Сорочан С.В. О регулярных композициях наследственных классов цветных графов // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10. № 1. С. 79–104.
27 . Алексеев В.Е., Мокеев Д.Б. Кёниговы графы относительно 3-путей // Дискретный анализ и исследование операций. 2012. Т. 19. № 4. C. 3–14.
28 . Ding G., Xu Z., Zang W. Packing cycles in graphs, II // Journal of Combinatorial Theory. Ser. B. 2003. V. 87. P. 244–253.