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

D. Malyshev

?

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

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.

Научное направление: Математика Компьютерные науки

Приоритетные направления: компьютерно-математическое математика

Язык: английский

Полный текст

Ключевые слова: hereditary class of graphs efficient algorithm edge 3-colorability Computational Complexity

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Исследование "критических" наследственных классов графов (2013)

Efficient Computation of Tolerances in the Weighted Independent Set Problem for Trees

Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368–371

The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...

Добавлено: 23 июня 2013 г.

Classes of graphs critical for the edge list-ranking problem

Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2014 Vol. 8 No. 2 P. 245–255

Добавлено: 8 мая 2014 г.

Complexity classification of the edge coloring problem for a family of graph classes

Малышев Д. С., Discrete Mathematics and Applications 2017 Vol. 27 No. 2 P. 97–101

Добавлено: 10 мая 2017 г.

The weighted coloring problem for two graph classes characterized by small forbidden induced structures

Малышев Д. С., Discrete Applied Mathematics 2018 Vol. 247 P. 423–432

Добавлено: 23 апреля 2018 г.

A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

Малышев Д. С., Discrete Applied Mathematics 2016 Vol. 203 P. 117–126

Добавлено: 9 октября 2015 г.

Critical hereditary graph classes: a survey

Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593–1612

Добавлено: 18 декабря 2015 г.

Expanding Operators for the Independent Set Problem

...

Добавлено: 3 октября 2013 г.

Classes of Subcubic Planar Graphs for Which the Independent Set Problem Is Polynomially Solvable

Добавлено: 21 января 2014 г.

Two complexity results for the vertex coloring problem

Малышев Д. С., Развенская О. О., Discrete Applied Mathematics 2017 Vol. 219 P. 158–166

Добавлено: 21 ноября 2016 г.

Efficient Computation of Tolerances in the Weighted Independent Set Problem for Some Classes of Graphs

Малышев Д. С., Пардалос П. О., Doklady Mathematics 2014 Vol. 89 No. 2 P. 253–256

Добавлено: 18 апреля 2014 г.

Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem

Добавлено: 30 января 2021 г.

The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs

Малышев Д. С., Graphs and Combinatorics 2017 Vol. 33 No. 4 P. 1009–1022

Добавлено: 26 мая 2017 г.

Two cases of polynomial-time solvability for the coloring problem

Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 31 No. 2 P. 833–845

Добавлено: 18 сентября 2014 г.

The computational complexity of three graph problems for instances with bounded minors of constraint matrices

Грибанов Д. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 227 P. 13–20

Добавлено: 23 апреля 2017 г.

The coloring problem for classes with two small obstructions

Малышев Д. С., / Series math "arxiv.org". 2013. No. 1307.0278v1.

Добавлено: 3 октября 2013 г.

A complexity dichotomy and a new boundary class for the dominating set problem

Малышев Д. С., Journal of Combinatorial Optimization 2016 Vol. 32 No. 1 P. 226–243

Добавлено: 4 апреля 2015 г.

Critical Elements in Combinatorially Closed Families of Graph Classes

Добавлено: 13 февраля 2017 г.

The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable

Малышев Д. С., Optimization Letters 2021 Vol. 15 No. 2 P. 311–326

Добавлено: 6 января 2021 г.

Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes

Развенская О. О., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2021 Vol. 15 No. 1 P. 97–117

Добавлено: 23 апреля 2021 г.

Полиномиальная разрешимость задачи о независимом множестве в классе графов без порожденных простых пути и цикла с пятью вершинами и большой клики

Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58–64

В работе предлагается алгоритм, который определяет число независимости n-вершинного графа из класса Free({P5,C5, Kp}) за время O(np+O(1)). ...

Добавлено: 6 июня 2012 г.

Boundary graph classes for some maximum induced subgraph problems

Малышев Д. С., Journal of Combinatorial Optimization 2014 Vol. 27 No. 2 P. 345–354

The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or ...

Добавлено: 7 февраля 2013 г.

Deciding the existence of minority terms

Kazda A., Opršal J., Valeriote M. и др., Canadian Mathematical Bulletin 2020 P. 577–591

Добавлено: 15 июня 2020 г.

A Cookbook for Temporal Conceptual Data Modelling with Description Logics

Artale A., Kontchakov R., Ryzhikov V. и др., ACM Transactions on Computational Logic 2014 Vol. 15 No. 3 P. 25.1–25.50

We design temporal description logics (TDLs) suitable for reasoning about temporal conceptual data models and investigate their computational complexity. Our formalisms are based on DL-Lite logics with three types of concept inclusions (ranging from atomic concept inclusions and disjointness to the full Booleans), as well as cardinality constraints and role inclusions. The logics are interpreted over the ...

Добавлено: 25 марта 2015 г.

Two-Station Single-Track Railway Scheduling Problem With Trains of Equal Speed

Гафаров Е. Р., Долгий А., Лазарев А. А., / Series -- "Computers & Industrial Engineering". 2014.

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains ...

Добавлено: 10 апреля 2015 г.