• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
July 20, 2026
Scientists Create Open Dataset for Studying Concentration
A team of Russian researchers, including scientists from HSE University–St Petersburg, has developed the first open multimodal dataset containing recordings of brain activity, heart function, and video observations to help researchers understand what happens in the human brain during deep concentration. In the future, the dataset could accelerate the development of neural interfaces, rehabilitation technologies, and AI systems. The article has been published in Scientific Data.
July 20, 2026
‘Science Is Universal-It Knows No Borders
Fuad Aleskerov, Tenured Professor and Director of the International Centre of Decision Choice and Analysis at HSE University, together with his colleagues, has developed methods of network analysis in bibliometrics that have made it possible to identify patterns in the appearance and citation of publications in academic journals, as well as their influence on each other. When one or a number of studies are frequently cited by a wide range of journals, this is an indicator that the research is of high quality. By contrast, extensive cross-citation within a limited group of journals increases the likelihood of identifying a network of predatory publications.
July 20, 2026
Scientists Propose Method for More Efficient Resource Use in Machine Learning
An international group of researchers, including mathematicians from the AI and Digital Science Institute at the HSE Faculty of Computer Science, has provided a theoretical justification for a simple and computationally efficient method of estimating uncertainty in Stochastic Gradient Descent (SGD). The paper has been published on the scientific preprint server arXiv.org and presented at AISTATS 2026.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests

Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций"). 2022. Vol. 16. P. 276–291.
Malyshev D., Duginov O. I.

The edge-coloring problem is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. The complexity status of this problem is known for all the classes defined by the sets of forbidden subgraphs with 7 edges each. In this paper, we consider the case of prohibitions with 8 edges. It can readily be seen that the edge-coloring problem is NP-complete for such a class if there are no subcubic forests among its 8-edge prohibitions. We prove that forbidding any subcubic 8-edge forest generates a class with polynomial-time solvability of the edge-coloring problem, except for the cases formed by the disjoint sum of one of four forests and an empty graph. For all the remaining cases, we prove a similar result for the intersection with the set of graphs with a maximum degree of at least four.

Research target: Mathematics Computer Science
Language: English
DOI
Text on another site
Keywords: Computational Complexityedge coloring problemmonotone class
Similar publications
Kolmogorov Operators and Their Applications
Springer Singapore (Singapore), 2024.
Included in the following conference series: INdAM: INdAM Meeting: Kolmogorov Operators and their Applications Workshop Conference proceedings info: INdAM 2022 Kolmogorov equations are a fundamental bridge between the theory of partial differential equations and that of stochastic differential equations that arise in several research fields. This volume collects a selection of the talks given at the Cortona meeting by ...
Added: July 17, 2026
Existence and uniqueness results for strongly degenerate McKean-Vlasov equations with rough coefficients
Veretennikov A., Pascucci A., Rondelli A., Stochastic Processes and their Applications 2026 Vol. 199 Article 104978
We present existence results for weak solutions to a broad class of degenerate McKean-Vlasov equations with rough coefficients, expanding upon and refining the techniques recently introduced by the third author. Under certain structural conditions, we also establish results concerning both weak and strong well-posedness. ...
Added: July 17, 2026
О сильных решениях многомерных СДУ с диагональными матрицами диффузии
Veretennikov A., Ляппиева А. А., Теория вероятностей и ее применения 2026 Т. 71 № 2 С. 295–304
Установлен новый результат о сильной единственности для многомерного СДУ с невырожденной диффузией и частично нерегулярным сносом. Его можно рассматривать как комбинированный вариант на темы Ямада и Ватанабэ (1971), Звонкина (1974) и первого автора настоящей статьи (1980). ...
Added: July 17, 2026
Об условиях для центральной предельной теоремы Добрушина для неоднородных цепей Маркова
Veretennikov A., Нуриева А. И., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 525 С. 24–30
Предложено новое достаточное условие в задаче о центральной предельной теореме в схеме серий для неоднородных цепей Маркова, с возможностью того, что минимум эргодического коэффициента Маркова–Добрушина может быть ближе к нулю, чем в основном условии Добрушина. ...
Added: July 17, 2026
О частных производных модифицированных полиномов Бернштейна–Станку для функций нескольких переменных
Veretennikov A., Мазутский Н. М., Математический сборник 2025 Т. 216 № 7 С. 3–27
Целью работы является доказательство аппроксимации смешанных производных второго порядка для функции нескольких переменных в норме L1 такими же производными модифицированных полиномов Бернштейна–Станку при минимальной возможной регулярности. ...
Added: July 17, 2026
О законе больших чисел для неодинаково распределенных слабо зависимых слагаемых
Ахмярова А. Т., Veretennikov A., Теория вероятностей и ее применения 2025 Т. 70 № 2 С. 211–227
В работе предложены новые версии слабого закона больших чисел (ЗБЧ) для слабо зависимых слагаемых (вообще говоря, разнораспределенных) как при наличии математического ожидания каждого из них, так и без такового. Одним из основных условий в первом из трех рассматриваемых случаев, в котором развиваются идеи из статьи Ю. Ш. Чау 1971 г., является равномерная интегрируемость слагаемых по Чезаро в духе работ по ЗБЧ для ...
Added: July 17, 2026
On weak existence of solutions of degenerate McKean-Vlasov equations
Veretennikov A., Stochastics and Dynamics 2024
A new weak existence result for degenerate multi-dimensional stochastic McKean–Vlasov equation is established under relaxed regularity conditions. ...
Added: July 17, 2026
Об усиленном законе больших чисел для попарно независимых случайных величин
Ахмярова А. Т., Veretennikov A., Теория вероятностей и ее применения 2024 Т. 69 № 3 С. 427–438
Предложен новый вариант усиленного закона больших чисел для попарно независимых случайных величин. Основная цель — ослабить требование существования математического ожидания каждого из слагаемых. Предположение о попарной независимости также ослаблено. ...
Added: July 17, 2026
On Higher Order Moments and Rates of Convergence for SDEs with Switching
Veretennikov A., Moscow Mathematical Journal 2024 Vol. 24 No. 1 P. 107–124
Second order recurrence are established for a d-dimensional diffusion with an additive Wiener process, with switching, and with one recurrent and one transient regime and constant switching intensities, under suitable conditions. As a corollary, the rate of convergence towards the invariant regime of order t^{−2} is claimed. The approach is based on embedded Markov chains ...
Added: July 16, 2026
On Positive Recurrence of the Mn/GI/1/∞ Model
Veretennikov A., Mathematics 2023 Vol. 11 No. 21 Article 4514
Positive recurrence for a single-server queueing system is established under generalized service intensity conditions, without the assumption of the existence of a service density distribution function, but with a certain integral type lower bound as a sufficient condition. Positive recurrence implies the existence of the invariant distribution and a guaranteed slow convergence to it in ...
Added: July 16, 2026
On averaged expected cost control for 1D controlled ergodic diffusions with switching
Veretennikov A., Markov Processes and Related Fields 2023 Vol. 23 No. 2 P. 259–294
The ergodic Bellman's (HJB) equation is proved for a one-dimensional controlled diffusion with switching with variable diffusion and drift coefficients both depending on control; the intensities of transitions of the discrete component are constant. Its existence and uniqueness is established. Also, the convergence of the reward iteration improvement algorithm is established to the cost constant ...
Added: July 16, 2026
WSI-GT: Pseudo-Label Guided Graph Transformer for Whole-Slide Histology
Михайлов И. А., Machine Learning and Knowledge Extraction 2026 Vol. 8 No. 1 Article 8
Whole-slide histology images (WSIs) can exceed 100 k × 100 k pixels, making direct pixel-level segmentation infeasible and requiring patch-level classification as a practical alternative for downstream WSI segmentation. However, most approaches either treat patches independently, ignoring spatial and biological context, or rely on deep graph models prone to oversmoothing and loss of local tissue ...
Added: July 16, 2026
On recurrence, convergence and mixing rate for generalised Wright - Fisher's diffusion with mutation
Veretennikov A., Sineokiy R., Markov Processes and Related Fields 2023 Vol. 23 No. 2 P. 241–258
Generalised one-dimensional Fisher -- Wright diffusion process with mutations is consiedered. This is a well-known model in populational genetics. The goal of the paper is an exponential recurrence of the process, which also implies exponential rate of convergence towards the invariant measure. ...
Added: July 16, 2026
Polynomial Recurrence for SDEs with a Gradient-Type Drift, Revisited
Veretennikov A., Mathematics 2023 Vol. 11 No. 14 Article 3096
Polynomial recurrence bounds for a class of stochastic differential equations with a rotational symmetric gradient type drift and an additive Wiener process are established, as well as certain a priori moment inequalities for solutions. The key feature of this paper is that the approach does not use Lyapunov functions because it is not clear how ...
Added: July 16, 2026
On the construction of Barnes–Wall lattices and their application in cryptography
Kuninets A., Malygina E., Leevik A. G. et al., Journal of Computer Virology and Hacking Techniques 2026 No. 22 Article 62
In this work, we investigate the application of Barnes–Wall lattices in post-quantum cryptographic schemes. We survey and analyze several constructions of Barnes–Wall lattices, including subgroup chains, the generalized k-ing construction, and connections with Reed-Muller codes, highlighting their equivalence over both Z[i] and Z. Building on these structural insights, we introduce a new algorithm for efficient ...
Added: July 16, 2026
On functional equations for Chow polylogarithms
Bolbachan V., / Series math "arxiv.org". 2024.
Chow polylogarithms are some special functions arising in explicit description of the Beilinson regulator map. The most interesting functional equation for this function reflects its vanishing on the boundary in the Bloch's cycle complex. We show that this functional equation formally follows from more simple ones, namely skew-symmetry, functoriality and multiplicativity. To prove this, we study ...
Added: July 16, 2026
On Goncharov’s conjecture in next to Milnor degree
Bolbachan V., / Series math "arxiv.org". 2024.
Let K be a field of characteristic zero. We prove that its motivic cohomology in degree m−1 and weight m is rationally isomorphic to the cohomology of the polylogarithmic complex. This gives a partial extension of A. Suslin theorem describing the indecomposable K3 of a field. ...
Added: July 16, 2026
Linear orders in Presburger arithmetic
Zapryagaev A., Pahomov F., Logic Journal of the IGPL 2026 Vol. 34 No. 4 Article 12
We prove the linear orders first-order definable in the standard model (Z;<,+) of Presburger arithmetic are exactly those that are (Z;<,+)-definably embeddable into the lexicographic ordering on Z^n for some ⁠n. ...
Added: July 16, 2026
On Markov–up processes and their recurrence properties
Veretennikov A., Veretennikova M., Reliability: Theory & Applications 2022 Vol. 17 No. 3(69) P. 273–291
A simple model of the new notion of ``Markov up'' processes is proposed; its positive recurrence and ergodic properties are shown under the appropriate conditions. ...
Added: July 16, 2026
Positive recurrence of a solution of an SDE with variable switching intensities
Veretennikov A., Stochastics and Partial Differential Equations: Analysis and Computations 2022 Vol. 10 P. 1165–1179
Positive recurrence of a $d$-dimensional diffusion with an additive Wiener process, with switching and with one recurrent and one transient regimes and variable switching intensities is established under suitable conditions. The approach is based on embedded Markov chains. ...
Added: July 15, 2026
An open problem about the rate of convergence in Erlang-Sevastyanov’s model
Veretennikov A., Queueing Systems 2022 Vol. 100 No. 3-4 P. 357–359
B.A. Sevastyanov's result about Erlang telephone station problem has been extended in several publications. In this short note one open question about this model has been discussed. The whole volume was devoted mainly to open problems related to the name of Erlang. ...
Added: July 15, 2026
Dynamical origin of extreme events in mutually coupled and networked Brusselator
Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 2026 Vol. 114 No. 1 P. 014217–014217
This study investigates the dynamical origins and statistical properties of extreme events (EEs) in a diffusively coupled theoretical Brusselator system, extending from pairwise interactions to globally coupled networks. Statistically, the emergence of EEs is characterized by heavy-tailed probability density functions and exponential interevent interval distributions, alongside an analysis of the complementary cumulative distribution function and ...
Added: July 15, 2026
On efficient algorithms for bottleneck path problems with many sources
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or max min ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise ...
Added: April 18, 2024
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Malyshev D., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain ...
Added: February 16, 2024
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit