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 :
بازگشت