Record number :

1600751

Title of article :

Vertex arboricity of toroidal graphs with a forbidden cycle

Author/Authors :

Choi، نويسنده , , Ilkyoo and Zhang، نويسنده , , Haihui، نويسنده ,

Issue Information :

روزنامه با شماره پیاپی سال 2014

Pages :

5

From page :

101

To page :

105

Abstract :

The vertex arboricity a ( G ) of a graph G is the minimum k such that V ( G ) can be partitioned into k sets where each set induces a forest. For a planar graph G , it is known that a ( G ) ≤ 3 . In two recent papers, it was proved that planar graphs without k -cycles for some k ∈ { 3 , 4 , 5 , 6 , 7 } have vertex arboricity at most 2. For a toroidal graph G , it is known that a ( G ) ≤ 4 . Let us consider the following question: do toroidal graphs without k -cycles have vertex arboricity at most 2? It was known that the question is true for k = 3 , and recently, Zhang proved the question is true for k = 5 . Since a complete graph on 5 vertices is a toroidal graph without any k -cycles for k ≥ 6 and has vertex arboricity at least three, the only unknown case was k = 4 . We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.

Keywords :

Vertex arboricity , Toroidal graphs , Discharging

Journal title :

Discrete Mathematics

Journal title :

Discrete Mathematics

Serial Year :

2014

Link To Document :