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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.endm.2009.11.032 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
transversal,H-transversal,H-subgraph,H-free graph | Journal | 35 |
Issue | ISSN | Citations |
1.0 | 1571-0653 | 1 |
PageRank | References | Authors |
0.40 | 3 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
M. Groshaus | 1 | 1 | 0.40 |
Pavol Hell | 2 | 2638 | 288.75 |
Sulamita Klein | 3 | 308 | 32.86 |
L.T. Nogueira | 4 | 1 | 0.40 |
F. Protti | 5 | 24 | 2.13 |