Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1708566 | Applied Mathematics Letters | 2012 | 5 Pages |
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
Timothy J. Hetherington,