RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. электрон. матем. изв., 2014, том 11, страницы 811–822 (Mi semr525)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Дискретная математика и математическая кибернетика

The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices

D. S. Malyshevab

a Lobachevsky State University of Nizhny Novgorod, 23 Gagarina Avenue, Nizhny Novgorod, 603950, Russia
b National Research University Higher School of Economics, 25/12 Bolshaja Pecherskaja Ulitsa, Nizhny Novgorod, 603155, Russia

Аннотация: We obtain a complete complexity dichotomy for the edge 3-colorability within the family of hereditary classes defined by forbidden induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures.

Ключевые слова: computational complexity, edge 3-colorability, hereditary class, efficient algorithm.

Полный текст: PDF файл (542 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.178
MSC: 05C15, 05С85
Поступила 30 ноября 2013 г., опубликована 12 ноября 2014 г.
Язык публикации: английский

Образец цитирования: D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 11 (2014), 811–822

Цитирование в формате AMSBIB
\RBibitem{Mal14}
\by D.~S.~Malyshev
\paper The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
\jour Сиб. электрон. матем. изв.
\yr 2014
\vol 11
\pages 811--822
\mathnet{http://mi.mathnet.ru/semr525}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr525
  • http://mi.mathnet.ru/rus/semr/v11/p811

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Д. С. Малышев, “Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов”, Дискрет. матем., 28:2 (2016), 44–50  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Discrete Math. Appl., 27:2 (2017), 97–101  crossref  isi
    2. D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discret Appl. Math., 219 (2017), 158–166  crossref  mathscinet  zmath  isi  scopus
    3. E. Galby, P. T. Lima, D. Paulusma, B. Ries, “Classifying k-edge colouring for h-free graphs”, Inf. Process. Lett., 146 (2019), 39–43  crossref  mathscinet  zmath  isi  scopus
  • Просмотров:
    Эта страница:156
    Полный текст:41
    Литература:34
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020