We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.

  • A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

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

Event ended

Speaker: Olga Razvenskaya, second-year PhD student, Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod)
Where: https://zoom.us/j/442268392  
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.