19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On a $P_k$-free colouring

Presented by Dr. Gabriel SEMANIšIN
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs


We study a special case of Vertex Deletion Problem: Find a minimum weight set of vertices of a given graph whose deletion gives a graph satisfying a given property. A subset $S$ of vertices of a graph $G$ is called a {\em $k$-path vertex cover} if the graph $G\setminus S$ is $P_k$-free. The minimum cardinality of a $k$-path vertex cover in $G$ is denoted $\psi_k(G)$. We show that the problem of determining $\psi_k(G)$ is NP-hard for each $k\geq2$, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of $\psi_k(G)$ and provide several estimations and exact values of $\psi_k(G)$. We also prove that $\psi_3(G)\le (2n+m)/6$, for every graph $G$ with $n$ vertices and $m$ edges. Moreover, we provide some exact and approximation algorithms for determining the value of $\psi_k$ for some classes of graphs.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

  • Dr. Gabriel SEMANIšIN Institute of Computer Science, P.J. Šafárik University, Faculty of Science, Košice, Slovakia