PhD Seminar: Some Hereditary Cases of Polynomial and Pseudopolynomial Solvability of the Graph Vertex Coloring Problem

Мероприятие завершено

Speaker: Olga Razvenskaya, second-year PhD student, Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod)
When: April 19, 18:10–19:30 

The vertex coloring problem (briefly, the VC problem) is to color vertices of a given graph in the minimum number of colors so that any two adjacent vertices have different colors. Its weighted version (briefly, the WVC problem) consists in coloring vertices in the minimum number of colors so that distinct colors are assigned to each vertex, the number of which is equal to the specified vertex weight, and different colors are assigned to adjacent vertices.

To construct efficient algorithms for solving the WVC problem, several methods of data reduction have been proposed. In the talk, a survey of classical graph reduction methods (such as the modular graph decomposition and the graph decomposition by separating cliques) will be made and new such techniques will be proposed.

A set of graphs closed under isomorphism and vertex removal is called a hereditary graph class. Each such a class can be defined by the set of its forbidden induced subgraphs. Some results are known on the complexity of the (W)VC problem in hereditary classes defined by small-size prohibitions. New results of this kind will be presented in this talk.