Equivalent Definitions for Block Elimination Distance and a Polynomial Kernel

Block elimination distance is a parameter on graphs that measures the distance of the biconnected components of a graph from a given class of graphs. When the indicated graph class is the class of edgeless graphs, we call the parameter block treedepth. In this thesis, we prove that block treedepth is equivalent to the minimum number of colors needed to color a graph such that every biconnected subgraph has a vertex of unique color. Additionally, we introduce a special kind of non-proper edge coloring that can serve as an alternative for block treedepth, called cycle edge ranking. Moreover, we make a connection between block treedepth and graph searching games by introduc- ing two versions of the cops and robbers game that can be used to calculate the block treedepth of a graph. Finally, we prove that block treedepth has a polynomial kernel when parameterized by the vertex cover number.