Efficient Solvability of the Weighted Vertex Coloring Problem for Some Hereditary Class of Graphs with $$\boldsymbol {5}
- PDF / 568,560 Bytes
- 10 Pages / 612 x 792 pts (letter) Page_size
- 55 Downloads / 220 Views
cient Solvability of the Weighted Vertex Coloring Problem for Some Hereditary Class of Graphs with 5-Vertex Prohibitions D. V. Gribanov1, 2* , D. S. Malyshev1, 2** , and D. B. Mokeev2, 1*** 1
National Research University “Higher School of Economics,” ul. Bolshaya Pecherskaya 25/12, Nizhny Novgorod, 603155 Russia 2
Lobachevsky State University of Nizhny Novgorod, pr. Gagarina 23, Nizhny Novgorod, 603950 Russia Received July 25, 2019; in final form, January 6, 2020; accepted February 19, 2020
Abstract—We consider the problem of minimizing the number of colors in the colorings of the vertices of a given graph so that, to each vertex there is assigned some set of colors whose number is equal to the given weight of the vertex; and adjacent vertices receive disjoint sets. For all hereditary classes defined by a pair of forbidden induced connected subgraphs on 5 vertices but four cases, the computational complexity of the weighted vertex coloring problem with unit weights is known. We prove the polynomial solvability on the sum of the vertex weights for this problem and the intersection of two of the four open cases. We hope that our result will be helpful in resolving the computational complexity of the weighted vertex coloring problem in the above-mentioned forbidden subgraphs. DOI: 10.1134/S1990478920030072 Keywords: weighted vertex coloring problem, hereditary class, computational complexity
INTRODUCTION We consider simple graphs, i.e. undirected unlabeled graphs without loops and multiple edges. The Weighted Vertex Coloring Problem (further, briefly, WVC) for a graph G = (V, E) and function w : V → N consists in finding the minimal number k (denoted by χw (G)) such that there exists a mapping c : V → 2{1,2,...,k} for which |c(v)| = w(v) for every v ∈ V and c(u) ∩ c(v) = ∅ for every uv ∈ E. The unweighted version (i.e., with unit vertex weights) of WVC is called the Vertex Coloring Problem (henceforth, VC). In other words, VC consists in finding the minimum number of sets of pairwise nonadjacent vertices (called independent) into which the vertex set of the given graph can be partitioned. A clique in a graph is a subset of pairwise adjacent vertices. VC and WVC on graphs are classical NP-complete problems [1]. A graph class is a set of graphs closed under isomorphism. A graph class is called hereditary if it is closed under vertex removal. It is well known that every hereditary graph class X can be defined by the set of its forbidden induced subgraphs Y, and this is written as follows: X = Free(Y). The graphs of the class X are also called Y-free. The VC problem is polynomially solvable for the class Free({H}) if H is an induced subgraph of the graph P4 or P3 + K1 ; otherwise, it is NP-complete in the given class (see [2]). However, if two induced subgraphs are forbidden then it is already impossible to obtain a complete complexity classification. For example, for all but three hereditary classes defined by prohibitions with at most 4 vertices each, the complexity status of VC is known (see [3]). For the remaining three cas
Data Loading...
