کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1708566 1012828 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List total arboricity of 2-degenerate graphs
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مکانیک محاسباتی
پیش نمایش صفحه اول مقاله
List total arboricity of 2-degenerate graphs
چکیده انگلیسی

The vertex arboricity ρ(G)ρ(G) of a graph GG is the smallest number of colours required to colour the vertices of GG such that no cycle is monochromatic. The list vertex arboricity ρl(G)ρl(G) is the list-colouring version of this concept. In this paper it is proved for the total graph T(G)T(G) of GG that if GG is a 22-degenerate graph with maximum degree Δ(G)Δ(G), then ⌈(Δ(G)+1)/2⌉≤ρ(T(G))≤ρl(T(G))≤⌈(Δ(G)+2)/2⌉⌈(Δ(G)+1)/2⌉≤ρ(T(G))≤ρl(T(G))≤⌈(Δ(G)+2)/2⌉. This shows that ρ(T(G))=ρl(T(G))ρ(T(G))=ρl(T(G)) when Δ(G)Δ(G) is even.We prove further that ρ(T(G))=ρl(T(G))=⌈(Δ(G)+1)/2⌉ρ(T(G))=ρl(T(G))=⌈(Δ(G)+1)/2⌉ if GG is a cycle, or a tree with Δ(G)≥2Δ(G)≥2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics Letters - Volume 25, Issue 12, December 2012, Pages 2018–2022
نویسندگان
,