CASCB talk: by Zuko Herz Fellows Mahsa Mozafary und Anteneh Getachew

Mahsa Mozafary und Anteneh Getachew, ZUKOnnect and Herz Fellows, University of Konstanz

CASCB talk by Zuko Herz Fellows Mahsa Mozafary und Anteneh Getachew

Bounds for the Path Vertex Cover Problem via Graph Coloring

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. In this context, the objects are called nodes or vertices and the relations are represented as lines (also called edges). Extremal graph theory as a branch of graph theory is studying some properties of graphs. One of the goals is to identify lower or upper bounds for a given property. In this research project, we are going to improve known lower and upper bounds for the k-path vertex cover problem by considering certain types of graph coloring. Graph coloring is a concept in extremal graph theory in which we assign (color) labels to vertices of the graph subject to some constraints, for example, that no two vertices connected with an edge share the same color. In the k-path vertex cover problem, the goal is covering all paths of length k or more in a given graph using a concise subset of vertices. The size of the smallest set with this property is called the k-path vertex cover number of the graph. The k-path vertex cover problem is a generalization of the classical vertex cover problem and naturally inherits its hardness. However, it is likely that the problem is even harder to approximate than the vertex cover special case. Star coloring and defective coloring are two types of vertex coloring that appear to be connected to the concept of path vertex cover problems. We are investigating these colorings on certain graph classes to learn more about the relationships between those two problems. Moreover, we are looking for path vertex cover number of special graphs such as Kneser graphs KG(n, r). So far we have found the exact k-path vertex cover number of KG(n, 2).