### ?

## Vertex colorings of graphs with few obstructions

Lozin V. V., Malyshev D.

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 three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.

Language:
English

Publication based on the results of:

Lozin V. V., Malyshev D., 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 ...

Added: March 3, 2015

Malyshev D., 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 ...

Added: March 6, 2014

Malyshev D., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833-845

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes. ...

Added: September 18, 2014

Malyshev D., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.

The coloring problem is studied in the paper for graph classes deﬁned by two small forbidden induced subgraphs. We prove some suﬃcient conditions for eﬀective 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 ﬁve vertices except ...

Added: October 3, 2013

Malyshev D., Graphs and Combinatorics 2017 Vol. 33 No. 4 P. 1009-1022

We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull ...

Added: May 26, 2017

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

Lebedeva A., Фундаментальная и прикладная математика 2014 Т. 19 № 2 С. 125-149

This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value m(k,n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each ...

Added: July 19, 2015

Malyshev D., Journal of Combinatorial Optimization 2016 Vol. 32 No. 1 P. 226-243

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with ...

Added: April 4, 2015

Malyshev D., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. ...

Added: April 7, 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

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

Lozin V. V., Malyshev D., Mosca R. et al., Theoretical Computer Science 2017 Vol. 700 P. 63-74

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On ...

Added: August 28, 2017

Grines V., Malyshev D., Pochinka O. et al., Regular and Chaotic Dynamics 2016 Vol. 21 No. 2 P. 189-203

It is well known that the topological classification of structurally stable flows on surfaces as well as the topological classification of some multidimensional gradient-like systems can be reduced to a combinatorial problem of distinguishing graphs up to isomorphism. The isomorphism problem of general graphs obviously can be solved by a standard enumeration
algorithm. However, an efficient ...

Added: April 5, 2016

Malyshev D., Gribanov D., Discrete Optimization 2018 Vol. 29 P. 103-110

We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value. ...

Added: April 8, 2018

Vyalyi M., Дискретная математика 1991 Т. 3 № 3 С. 35-45

Added: October 17, 2014

Пенза : ПГУ, 2015

В сборник трудов включены доклады юбилейного ХХ-го Международного симпозиума «Надежность и качество», проходившего с 25 по 31 мая 2015 г. в городе Пензе.
Рассмотрены актуальные проблемы теории и практики повышения надежности и качества; эффективности внедрения инновационных и информационных технологий в фундаментальных научных и прикладных исследованиях, образовательных и коммуникативных системах и средах, экономике и юриспруденции; методов и ...

Added: May 31, 2015

Lanham : University Press of America, 2012

The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...

Added: February 13, 2013

Kuznetsov V. O., Логистика и управление цепями поставок 2018 № 4 (87) С. 27-33

One of the options for a more flexible approach to analyzing the reliability of supply chains is the principal component analysis (PCA). With a large number of variables describing supply chain, it is a difficult task to analyze the structure of variables in two-dimensional space. Within the analysis of the variables dependencies PCA allows to ...

Added: November 29, 2018

Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40-58

The complexity of realization of k-valued logic functions by circuits in a special infinite basis is under study. This basis consists of Post negation (i.e. function x+1(mod k)) and all monotone functions. The complexity of the circuit is the total number of elements of this circuit. For an arbitrary function f, we find the lower and upper bounds ...

Added: March 11, 2018

Akopov A. S., Beklaryan L. A., Saghatelyan A. K., Environmental Modelling and Software 2019 Vol. 116 P. 7-25

Urban greenery such as trees can effectively reduce air pollution in a natural and eco-friendly way. However, how to spatially locate and arrange greenery in an optimal way remains as a challenging task. We developed an agent-based model of air pollution dynamics to support the optimal allocation and configuration of tree clusters in a city. The Pareto ...

Added: February 24, 2019

Marshirov V. V., Marshirova L. E., Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111-120

The paper considers the problem of determining the rate of cooling of metal during solidification at the intersection of the liquidus temperature under intense heat sink from the surface. The solution to this problem it is necessary to determine the process conditions, the boundary and initial conditions for which it is possible to get new ...

Added: November 17, 2013

Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve ...

Added: January 30, 2021

Malyshev D., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130

Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...

Added: December 25, 2020