Preskoči na glavno vsebino

Simon Schmidt: Playing with distinguishing coloring

Datum objave: 24. 2. 2015
Seminar za teorijo grafov in algoritme
Četrtek 26. februar 2015 ob 12:15 v PS na Jadranski 19
Abstract: In this talk I will introduce a new game invariant for graphs, based on the distinguishing number. Two players, the Gentle and the Rascal are alternatively coloring the vertices of a graph G . The Gentle aims to build a distinguishing coloring and the Rascal try to stop him. The Game Distinguishing Number of G is the minimun of colours the Gentle needs to be sure to win the game. As we will show this invariant could be infinite. We will investigate several classes of graphs including even cycles, hypercubes and some cartesian products of complete graphs.