A Tight Erdös--Pósa Function for Wheel Minors
| Autor: | Jean Florent Raymond, Gwenaël Joret, Samuel Fiorini, Tony Huynh, Ignasi Sau, Pierre Aboulker |
|---|---|
| Přispěvatelé: | Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Département de mathématiques Université Libre de Bruxelles, Université libre de Bruxelles (ULB), Département d'Informatique, Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM) |
| Rok vydání: | 2018 |
| Předmět: |
Combinatorics
Discrete mathematics Mathematics::Probability 010201 computation theory & mathematics General Mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 010102 general mathematics 0102 computer and information sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 0101 mathematics 01 natural sciences Graph Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (3), pp.2302-2312. ⟨10.1137/17M1153169⟩ |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/17m1153169 |
| Popis: | International audience; Let $W_t$ denote the wheel on t+1 vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k \geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as a minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|