?
Colourings of uniform hypergraphs with large girth and applications
Combinatorics Probability and Computing. 2018. Vol. 27. No. 2. P. 245–273.
Шабанов Д. А., Kupavskii A.
Лебедева А. В., Фундаментальная и прикладная математика 2014 Т. 19 № 2 С. 125–149
Рассматривается экстремальная задача о раскрасках гиперграфов. Пусть k — натуральное число. Требуется найти величину m(k,n), равную минимальному количеству рёбер n-однородного гиперграфа, не допускающего таких двухцветных раскрасок множества вершин, что в каждом ребре гиперграфа содержатся по крайней мере k вершин каждого цвета. В работе получены верхние оценки величин m(k,n) для малых значений k, n, найдено значение ...
Добавлено: 19 июля 2015 г.
Шабанов Д. А., Балобанов А. Е., Математические заметки 2018 Т. 103 № 1 С. 38–48
В работе исследуются экстремальные задачи о числе j-независимых множеств в однородных простых гиперграфах. Получены близкие к оптимальным результаты для максимального количества независимых множеств в классе простых регулярных гиперграфов, а также для минимального числа - в классе простых гиперграфов с заданной средней степенью вершины. ...
Добавлено: 13 февраля 2018 г.
Шабанов Д. А., Akhmejanova M., Discrete Mathematics 2020 Vol. 343 No. 4 P. 1–11
Добавлено: 31 октября 2019 г.
Шабанов Д. А., Хузиева А. Э., Математические заметки 2015 Т. 98 № 6 С. 948–951
Работа посвящена изучению известной проблемы экстремальной комбинаторики, связанной с раскрасками гиперграфов. исследуется минимальное число ребер в n-однородном гиперграфе с обхватом более s и хроматическим числом более r. Обоснована новая нижняя оценка данной величины. ...
Добавлено: 4 сентября 2016 г.
Шабанов Д. А., Graphs and Combinatorics 2014 Vol. 30 No. 5 P. 1249–1260
Добавлено: 15 декабря 2015 г.
Шабанов Д. А., Kozik J., Journal of Combinatorial Theory. Series B 2016 Vol. 116 P. 312–332
Добавлено: 15 декабря 2015 г.
Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833–845
Добавлено: 18 сентября 2014 г.
Шабанов Д. А., Akolzin I., Discrete Mathematics 2016 Vol. 339 No. 12 P. 3020–3031
Добавлено: 4 сентября 2016 г.
Работа посвящена изучению пороговой вероятности наличия полноцветной раскраски в r цветов у случайного k-однородного гиперграфа в биномиальной модели H(n,k,p), т.е. такой раскраски, что каждое ребро гиперграфа содержит вершины всех r цветов. Показано, что данная пороговая вероятность при фиксированных r<k и растущем n отвечает разреженному случаю, т.е. случаю линейного среднего числа ребер cn для положительного фиксированного ...
Добавлено: 5 июня 2019 г.
Balobanov A., Шабанов Д. А., Discrete Mathematics 2021 Vol. 344 No. 3 Article 112231
Добавлено: 27 ноября 2020 г.
Шабанов Д. А., European Journal of Combinatorics 2015 Vol. 43 P. 185–203
Добавлено: 6 октября 2015 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545–3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Шабанов Д. А., Доклады Академии наук 2017 Т. 475 № 1 С. 24–28
В работе исследуется проблема нахождения предельного распределения хроматического числа случайного однородного гиперграфа в разреженном случае. Показано, что для большей части значений параметров модели предельное значение хроматического числа концентрируется ровно в одной точке, которая может быть явно вычислена. ...
Добавлено: 19 июля 2017 г.
Шабанов Д. А., Шайхеева Т. М., Математические заметки 2020 Т. 107 № 3 С. 454–465
Работа посвящена предписанным раскраскам однородных гиперграфов. Пусть H(m,r,k) - это полный r-дольный k-однородный гиперграф с равными размерами долей $m$, в котором каждое ребро содержит ровно по одной вершине из некоторых k<= r долей. С помощью результатов о кратных покрытиях независимыми множествами найдена асимптотика предписанного хроматического числа H(m,r,k) с ростом m для фиксированных k и r. ...
Добавлено: 14 июня 2020 г.
Добавлено: 15 ноября 2018 г.
Akhmejanova M., Шабанов Д. А., Discrete Applied Mathematics 2020 Vol. 276 P. 2–12
Добавлено: 31 октября 2019 г.
Шабанов Д. А., Семенов А. С., Дискретная математика 2016 Т. 28 № 3 С. 126–144
Изучается асимптотическое поведение числа независимости для биномиальной модели случайного k-однородного гиперграфа H(n, k, p) в разреженном случае, когда p = c (n-k)!(k-1)!/(n−1)! при положительном постоянном c > 0. Показано, что существует такая константа γ(c) > 0, что число независимости α(H(n, k, p)) подчиняется закону больших чисел α(H(n, k, p))/n → γ(c) при n → +∞. ...
Добавлено: 27 декабря 2016 г.
Шабанов Д. А., Хузиева А. Э., Дискретная математика 2015 Т. 27 № 2 С. 112–133
В работе исследуется экстремальная проблема комбинаторного анализа об отыскании минимально возможного количества ребер в $n$-однородном гиперграфе с хроматическим числом больше $r$ и обхватом больше $s$. Получена новая нижняя оценка подобной экстремальной величины, а также ряд смежных результатов. ...
Добавлено: 23 февраля 2016 г.
Cherkashin Danila, Discrete Mathematics 2018 Vol. 341 No. 3 P. 652–657
Добавлено: 30 января 2018 г.
Малышев Д. С., Optimization Letters 2014 Vol. 8 No. 8 P. 2261–2270
The coloring problem is studied in the paper for graph classes defined by two small forbidden induced subgraphs. We prove some sufficient conditions for effective solvability of the problem in such classes. As their corollary we determine the computational complexity for all sets of two connected forbidden induced subgraphs with at most five vertices except ...
Добавлено: 6 марта 2014 г.
Лозин В. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 216 P. 273–280
We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining ...
Добавлено: 3 марта 2015 г.