20.500.12556/RUP-17628 A note on acyclic number of planar graphs Opomba o acikličnem številu ravninskih grafov The acyclic number ▫$a(G)$▫ of a graph ▫$G$▫ is the maximum order of an induced forest in ▫$G$▫. The purpose of this short paper is to propose a conjecture that ▫$a(G)\geq \left( 1-\frac{3}{2g}\right)n$▫ holds for every planar graph ▫$G$▫ of girth ▫$g$▫ and order ▫$n$▫, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that ▫$a(G)\geq \left( 1-\frac{3}{g} \right)n$▫ holds. In addition, we give a construction showing that the constant ▫$\frac{3}{2}$▫ from the conjecture cannot be decreased. Aciklično število ▫$a(G)$▫ grafa ▫$G$▫ je maksimalni red induciranega gozda v ▫$G$▫. Namen tega kratkega članka je predstavitev domneve, da ▫$a(G)\geq \left( 1-\frac{3}{2g}\right)n$▫ velja za vsak ravninski graf ▫$G$▫ ožine ▫$g$▫ in reda ▫$n$▫, ki obsega tri znane hipoteze s tega področja. V podporo tej domnevi dokažemo šibkejši rezultat, da velja ▫$a(G)\geq \left( 1-\frac{3}{g} \right)n$▫. Poleg tega podamo konstrukcijo, ki pokaže, da konstante ▫$\frac{3}{2}$▫ iz te hipoteze ni mogoče zmanjšati. induced forest acyclic number planar graph girth induciran gozd aciklično število ravninski graf ožina true true false Angleški jezik Slovenski jezik Neznano 2022-01-03 01:13:15 2022-01-03 01:13:15 2024-03-01 14:39:22 0000-00-00 00:00:00 2017 0 0 str. 317-322 no. 2 Vol. 13 2017 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1855-3966 2048439059 RAZ_Petrusevski_Mirko_i2017.pdf RAZ_Petrusevski_Mirko_i2017.pdf 1 16221246B7AECF9331577AC35E4236C8 fa01fc757c17a746ccad3b708e7df3646e127492677c8e8eea1d6c4c8d4d6fad 7843310e-c3d6-11ed-b5df-005056bf369b https://repozitorij.upr.si/Dokument.php?lang=slv&id=25946 Založba Univerze na Primorskem 0 0 0