LIST POINT ARBORICITY OF GRAPHS
Authors:
- 21 June 2012
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Discrete Mathematics, Algorithms and Applications
- Vol. 04 (02)
Abstract
Let G be a graph. The point arboricity of G, denoted by ρ(G), is the minimum number of colors that can be used to color the vertices of G so that each color class induces an acyclic subgraph of G. Borodin et al. (Discrete Math.214 (2000) 101–112) first introduced the list point arboricity of G, denoted by ρl(G). We prove that for any graph G, [Formula: see text], where deg (G) denotes the degeneracy of G, that is, the minimum number k such that δ(H) ≤ k for any subgraph H of G. Using this upper bound, we show that ρl(G) ≤ 3 for any planar graph G. In particular, if either G is K4-minor free, or for an integer k ∈ {3, 4, 5, 6}, G is planar and does not contain k-cycles, then ρl(G) ≤ 2. For any graph G of order n, [Formula: see text]. In addition, we provide a new proof of a theorem of Borodin et al., which states that if G is neither a complete graph of odd order nor a cycle then [Formula: see text]. Finally, we show that la (G) = lla (G) = 2 if G is 3-regular, and la (G) = lla (G) = 3 if G is 4-regular, where la (G) is the linear arboricity of G and lla (G) is list linear arboricity of G which is introduced recently by An and Wu.Keywords
This publication has 14 references indexed in Scilit:
- On the vertex-arboricity of planar graphsEuropean Journal of Combinatorics, 2008
- Planar Graphs Without Cycles of Specific LengthsEuropean Journal of Combinatorics, 2002
- Variable degeneracy: extensions of Brooks’ and Gallai's theoremsDiscrete Mathematics, 2000
- Covering and packing in graphs IV: Linear arboricityNetworks, 1981
- Graph Theory with Applications1976
- On the Point-Arboricity of a Graph and its ComplementCanadian Journal of Mathematics, 1971
- COVERING AND PACKING IN GRAPHS, I.Annals of the New York Academy of Sciences, 1970
- The point-arboricity of a graphIsrael Journal of Mathematics, 1968
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965
- On Complementary GraphsThe American Mathematical Monthly, 1956