?
Almost all factorial subclasses of quasi-line graphs with respect to one forbidden subgraph
Moscow Journal of Combinatorics and Number Theory. 2011. Vol. 1. No. 3. P. 277-286.
Zamaraev V. A.
For a graph property X, let Xn be the set of graphs with the vertex set {1, . . . , n} that satisfy the property X. A property X is called factorial if X is hereditary (i. e. closed under taking induced subgraphs) and nc1n ≤ X ≤ nc2n for some positive constants c1 and c2. A graph G is a quasi-line if for every vertex v, the set of neighbors of v can be expressed as a union of two cliques. In the present paper we identify almost all factorial subclasses of quasi-line graphs defined by one forbidden induced subgraph. We use these new results to prove that the class Free(K1,3,W4) is factorial, which improves on a result of Lozin, Mayhill and Zamaraev [8].
Zamaraev V. A., Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 30-39
For a set of labeled graphs X, let Xn be the set of n-vertex graphs from X. Hereditary class X is called at most factorial if there exist positive constants c,n0 such that |Xn| < n^{cn} for all n > n0. Lozin's conjecture states that hereditary class X is at most factorial if and only ...
Added: November 18, 2013
Lozin V. V., Mayhil C., Zamaraev V. A., European Journal of Combinatorics 2012 Vol. 33 No. 4 P. 534-543
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Lozin V. V., Mayhil C., Zamaraev V. A., Electronic Journal of Combinatorics 2011 Vol. 18 No. 1 P. 1-14
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Lozin V. V., Dabrowski K., Zamaraev V. A., Discrete Mathematics 2012 Vol. 312 No. 16 P. 2457-2465
For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e., closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...
Added: June 28, 2012
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2011 Т. 6 № 1 С. 169-173
Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах. ...
Added: June 28, 2012
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2014 Т. 3 № 1 С. 288-290
В работе показывается, что задача о раскраске полиномиально разрешима в классе графов Free({claw,bull}). ...
Added: April 7, 2014
Alekseev V., Zamaraev V. A., Zakharova D. V. et al., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 6(1) С. 165-172
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: February 3, 2014
Malyshev D., Дискретная математика 2012 Т. 24 № 4 С. 91-103
В данной работе рассматриваются понятия минимального сложного и граничного классов. Данные классы играют особую роль при определении границы между полиномиальной разрешимостью и NP-полнотой задач на графах в семействе наследственных классов. Ранее в одной из работ автора было установлено, что для некоторого типа задач на графах минимальных сложных классов нет. В данной работе, наоборот,
доказывается достаточное условие ...
Added: May 17, 2013
Malyshev D., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81-96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Added: February 27, 2017
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2017 Vol. 11 No. 1 P. 99-106
The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the ...
Added: February 13, 2017
Malyshev D., Журнал Средневолжского математического общества 2020 Т. 22 № 1 С. 38-47
Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске ...
Added: March 26, 2020
Zamaraev V. A., В кн. : XVI Нижегородская сессия молодых ученых. Математические науки: Материалы докладов. Вып. 16.: Н. Новгород : Нижегородский государственный университет им. Н.И. Лобачевского, 2011. С. 26-27.
Описаны почти все факториальные подклассы класса квазиреберных графов, определяемые одним запрещенным графом. ...
Added: July 4, 2012
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2014 Vol. 8 No. 2 P. 245-255
The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem ...
Added: May 8, 2014
Malyshev D., Discrete Applied Mathematics 2016 Vol. 203 P. 117-126
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. ...
Added: October 9, 2015
Malyshev D., Discrete Applied Mathematics 2018 Vol. 247 P. 423-432
We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...
Added: April 23, 2018
Korpelainen N., Lozin V. V., Malyshev D. et al., Theoretical Computer Science 2011 No. 412 P. 3545-3554
The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...
Added: September 11, 2012
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Added: November 30, 2012
Atminas A., Collins A., Lozin V. et al., Discrete Mathematics 2015 Vol. 338 No. 2 P. 164-179
The idea of implicit representation of graphs was introduced in Kannan et al. (1992) and can be defined as follows. A representation of an n-vertex graph G is said to be implicit if it assigns to each vertex of G a binary code of length O(logn) so that the adjacency of two vertices is a function of their codes. Since an implicit ...
Added: March 16, 2015
Malyshev D., Pardalos P. M., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...
Added: December 18, 2015
Malyshev D., Razvenskaya O., Discrete Applied Mathematics 2017 Vol. 219 P. 158-166
We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.
Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs. ...
Added: November 21, 2016
Malyshev D., Siberian Electronic Mathematical Reports 2014 Vol. 11 P. 811-822
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. ...
Added: April 7, 2014
Alekseev V., Zakharova D. V., Malyshev D. et al., Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математика 2012 № 6(1) С. 115-120
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Added: May 17, 2013
Malyshev D., Дискретная математика 2012 Т. 24 № 2 С. 75-78
В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный ...
Added: November 30, 2012
191574970, Functional Analysis and Its Applications 2006 Vol. 40 No. 2 P. 81-90
It is well known that every module M over the algebra ℒ(X) of operators on a finite-dimensional space X can be represented as the tensor product of X by some vector space E, M ≅ = E ⊗ X. We generalize this assertion to the case of topological modules by proving that if X is a stereotype space with the stereotype approximation property, then for each stereotype module M over the ...
Added: September 23, 2016