A lower bound on the order of the largest induced forest in planar graphs with high girth

详细信息    查看全文

• 作者：Franç ; ois Dross^a ; ^{francois.dross@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding author} ; Mickael Montassier^b ; ^{mickael.montassier@lirmm.fr" class="auth_mail" title="E-mail the corresponding author} ; Alexandre Pinlou^c ; ^{alexandre.pinlou@lirmm.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Induced forest ; Feedback vertex set ; Large girth ; Planar graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 December 2016
• 年：2016
• 卷：214
• 期：Complete
• 页码：99-107
• 全文大小：446 K

文摘

We give here new lower bounds on the size of a largest induced forest in planar graphs with high girth. This is equivalent to upper bounds on the size of a smallest feedback vertex set. In particular, we prove that a planar graph with girth class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si13.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=3c2a86fc4f03897d36079ce01b84ca4b" title="Click to view the MathML source">gclass="mathContainer hidden">class="mathCode">$g$ and size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si20.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=5d355961c68c999e0ceb455324d1218d" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$ has a feedback vertex set of size at most class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si21.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=98990c71a951c3ef5c1cddbda5d460c8">class="imgLazyJSB inlineImage" height="23" width="17" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302906-si21.gif">class="mathContainer hidden">class="mathCode">$\frac{4m}{3g}$, improving the trivial bound of class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si22.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=24097a7cbbf5bb5a01ebd8884e3772a7">class="imgLazyJSB inlineImage" height="23" width="17" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302906-si22.gif">class="mathContainer hidden">class="mathCode">$\frac{2m}{g}$. We also prove that every class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si23.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=a93f859f0ec6c60094bbf0f668cab2a4" title="Click to view the MathML source">2class="mathContainer hidden">class="mathCode">$2$-connected graph with maximum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si24.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=d8e0c75fa4b665e0eb9e3af8b9da8850" title="Click to view the MathML source">3class="mathContainer hidden">class="mathCode">$3$ and order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si25.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=0edc1dbe05d850190d06cd1ddbb9cbfb" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ has a feedback vertex set of size at most class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16302906&_mathId=si26.gif&_user=111111111&_pii=S0166218X16302906&_rdoc=1&_issn=0166218X&md5=71e5a8fbc170beaca3ce75f0d607c989">class="imgLazyJSB inlineImage" height="21" width="23" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16302906-si26.gif">class="mathContainer hidden">class="mathCode">$\frac{n+2}{3}$.