Cycle transversals in bounded degree graphs

Groshaus, Marina Esther; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F.

info:eu-repo/semantics/article

Date

2009-12

Registration in:

Groshaus, Marina Esther; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F.; Cycle transversals in bounded degree graphs; Elsevier; Electronic Notes in Discrete Mathematics; 35; C; 12-2009; 189-195

1365-8050

http://hdl.handle.net/11336/68193

1571-0653

CONICET Digital

CONICET

https://repositorioslatinoamericanos.uchile.cl/handle/2250/4363769

Author

Groshaus, Marina Esther

Hell, P.

Klein, S.

Nogueira, L. T.

Protti, F.

Institutions

Consejo Nacional de Investigaciones Científicas y Tecnológicas (Argentina)

Abstract

In this work we consider the problem of finding a minimum Ck-transversal (a subset of vertices hitting all the induced chordless cycles with k vertices) in a graph with bounded maximum degree. In particular, we seek for dichotomy results as follows: for a fixed value of k, finding a minimum Ck-transversal is polynomial-time solvable if k ≤ p, and NP-hard otherwise.

Subjects

Show full item record