255 KB12 KB200820252017Petruševski, MirkoŠkrekovski, Risteletnik:13številka:2str. 317-322ISSN:1855-3966COBISSID:2048439059URN:URN:NBN:SI:doc-WE8D4U05enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaaciklično številoinduciran gozdožinaravninski grafteorija grafovA note on acyclic number of planar graphs|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 decreasedAciklič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šatiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije