Abstract: Let G be a vertex colored graph, the vertices are colored with black and white. The pressing game on G is the following. Any black vertex v can be pressed, and pressing v causes: - all of the neighbors of v changes color, black vertices become white, and white vertices become black; - all pair of neighbors of v changes connectivity, if two neighbors were connected, they become unconnected and vice versa; - v itself becomes an all white and separated vertex.
The aim of the game is to transform G into the all white, empty graph. It is known that such transformation is always possible if each component of G contains at least one black vertex. Such solutions are called successful pressing paths. It is also known that for any G, the
length of each successful pressing path is the same. The pressing game conjecture is the following. Let G be a black-and-white graph such that each component on it contains at least one black vertex. Construct a metagraph, M whose vertices are the successful pressing paths on G. Connect two vertices if the length of the longest common subsequence of the pressing paths they represent is
at most 4 less than the common length of the pressing paths. The conjecture is that M is connected.
We are going to show a proof for linear graph, and also the connection to genome rearrangement is discussed.
You can watch the lecture here: