论文标题
平面图的分数顶点 -
Fractional vertex-arboricity of planar graphs
论文作者
论文摘要
我们对平面图的分数顶点 - 贫困性进行了系统的研究，并证明了与分数着色和平面图中最大诱导森林的大小的开放问题的联系。特别是，以下三个长期的猜想涉及平面图中最大诱发森林的大小，我们猜想这些森林中的每一个都可以推广到分数顶点铝的设置。 In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Lužar, and Škrekovski conjectured that every planar graph of girth at least五个至少十分之一的顶点有诱发森林。我们通过证明每一个平面图至少五个平面图具有分数顶点 - 贫困性，最多最多$ 2-1/324 $，从而取得了进步。
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the following three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Lužar, and Škrekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$.
