Approximate min–max relations for odd cycles in planar graphs |
| |
| Authors: | Samuel Fiorini Nadia Hardy Bruce Reed Adrian Vetta |
| |
| Affiliation: | 1.GERAD – HEC Montréal,Montréal,Canada;2.Département de Mathématique,Université Libre de Bruxelles,Bruxelles,Belgium;3.Department of Mathematics and Statistics,McGill University,Montreal,Canada;4.School of Computer Science,McGill University,Montreal,Canada;5.Department of Mathematics and Statistics and School of Computer Science,McGill University,Montreal,Canada |
| |
| Abstract: | We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio is at most 10. For the corresponding edge version of this problem, Král and Voss recently proved that this ratio is at most 2; we also give a short proof of their result. This work was supported by FNRS, NSERC (PGS Master award, Canada Research Chair in Graph Theory, award 288334-04) and FQRNT (award 2005-NC-98649). |
| |
| Keywords: | Odd cycle transversal Odd cycle packing Planar graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
