کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647109 1632409 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Vertex arboricity of toroidal graphs with a forbidden cycle
ترجمه فارسی عنوان
آرتروزیت ورتکس گرافهای توریدال با یک چرخه ممنوعه
کلمات کلیدی
آرتوریکس ورتکس، نمودارهای توریدال، تخلیه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 333, 28 October 2014, Pages 101–105
نویسندگان
, ,