Induced packing of odd cycles in planar graphs

DOI10.1016/j.tcs.2011.11.004zbMath1232.68064MaRDI QIDQ764360

Daniël Paulusma, Marcin Kaminski, Petr A. Golovach, Dimitrios M. Thilikos

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.004

zbMATH Keywords

planar graphs; fixed parameter tractability; odd cycles; induced packing; irrelevant vertex technique

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)