Title of article :
List total arboricity of 2-degenerate graphs
Author/Authors :
Hetherington، نويسنده , , Timothy J.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2012
Pages :
5
From page :
2018
To page :
2022
Abstract :
The vertex arboricity ρ ( G ) of a graph G is the smallest number of colours required to colour the vertices of G such that no cycle is monochromatic. The list vertex arboricity ρ l ( G ) is the list-colouring version of this concept. In this paper it is proved for the total graph T ( G ) of G that if G is a 2 -degenerate graph with maximum degree Δ ( G ) , then ⌈ ( Δ ( G ) + 1 ) / 2 ⌉ ≤ ρ ( T ( G ) ) ≤ ρ l ( T ( G ) ) ≤ ⌈ ( Δ ( G ) + 2 ) / 2 ⌉ . This shows that ρ ( T ( G ) ) = ρ l ( T ( G ) ) when Δ ( G ) is even. ve further that ρ ( T ( G ) ) = ρ l ( T ( G ) ) = ⌈ ( Δ ( G ) + 1 ) / 2 ⌉ if G is a cycle, or a tree with Δ ( G ) ≥ 2 .
Keywords :
list colouring , total colouring , minor-free graph , outerplanar graph , Point arboricity
Journal title :
Applied Mathematics Letters
Serial Year :
2012
Journal title :
Applied Mathematics Letters
Record number :
1528588
Link To Document :
بازگشت