کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647109 | 1632409 | 2014 | 5 صفحه PDF | دانلود رایگان |
The vertex arboricity a(G)a(G) of a graph GG is the minimum kk such that V(G)V(G) can be partitioned into kk sets where each set induces a forest. For a planar graph GG, it is known that a(G)≤3a(G)≤3. In two recent papers, it was proved that planar graphs without kk-cycles for some k∈{3,4,5,6,7}k∈{3,4,5,6,7} have vertex arboricity at most 2. For a toroidal graph GG, it is known that a(G)≤4a(G)≤4. Let us consider the following question: do toroidal graphs without kk-cycles have vertex arboricity at most 2? It was known that the question is true for k=3k=3, and recently, Zhang proved the question is true for k=5k=5. Since a complete graph on 5 vertices is a toroidal graph without any kk-cycles for k≥6k≥6 and has vertex arboricity at least three, the only unknown case was k=4k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.
Journal: Discrete Mathematics - Volume 333, 28 October 2014, Pages 101–105