Article ID Journal Published Year Pages File Type
1708566 Applied Mathematics Letters 2012 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
,