On the vertex arboricity of planar graphs (2008)

Originators: André Raspaud and Weifan Wang    (presented by Lale Özkahya - REGS 2008)

Definitions: The vertex arboricity of a graph G, written a(G), is the minimum number of sets in a partition of V(G) into sets inducing forests. A linear forest is a forest in which every component is a path. The linear vertex arboricity of G, written la(G) is the minimum number of sets in a partition of V(G) into sets inducing linear forests.

Background: These parameters are examples of "generalized coloring parameters", where a hereditary family F is specified, and the corresponding coloring parameter for a graph G is the minimum number of sets in a partition of V(G) into sets inducing subgraphs that lie in F. Such parameters have been studied especially over the family of planar graphs. In the most general situation, different families may be associated with different colors, and one asks whether such a vertex partition exists

Conjecture 1: If G is a planar graph in which no two triangles share a vertex, then a(G)≤2.

Comments: Upper bounds on these parameters are known for various families of planar graphs.

• Chartrand-Kronk-Wall [CKW]: a(G)&le 3 when G is planar, and this is sharp.
• Poh [P]: la(G)≤3 when G is planar.
• Stein [S]: For a triangulation G with at least four vertices, a(G)=2 if and only if the dual graph G* is Hamiltonian.
• Raspaud-Wang [RW]: If k∈{3,4,5,6}, then a(G)≤2 for every planar graph G having no k-cycle.
• Raspaud-Wang [RW]: a(G)≤2 when G is planar and no two triangles have vertices that are shared or adjacent.
• Kronk-Mitchem [KM]: a(G)≤⌈Δ(G)/2⌉ when G is a connected graph that is neither a cycle nor a complete graph of odd order. (It is conjectured that la(G)≤⌈(Δ(G)+1)/2⌉.)

Question 2: What is the least k such that some planar graph with vertex arboricity 3 has no k-cycle? (In [RW], the value is shown to be between 7 and 22.

Conjecture 3: Every planar graph G has a vertex partition (V₁,V₂,V₃) such that V₁ and V₂ are independent sets and V₃ induces a forest.

Conjecture 4: Every planar graph G without 3-cycles has a vertex partition (V₁,V₂) such that V₁ is an independent set and V₂ induces a forest.

Comments: Conjecture 3 implies the Four Color Theorem. Raspaud and Wang [RW] showed that every planar graph has a vertex partition (V₁,V₂,V₃) such that V₁ is an independent set and each of V₂, V₃ induces a forest. Borodin and Glebov [BG] proved the conclusion of Conjecture 4 for planar graphs with girth at least 5, so only the case of girth 4 remains. Since forests are bipartite, Conjecture 4 implies Grötzsch's Theorem.

References:
[RW] A. Raspaud, W. Wang, On the vertex arboricity of planar graphs, European Jnl. of Combin. (2008), in press.
[BG] O.V. Borodin, A.N. Glebov, On the partition of a planar graph of girth 5 into an empty and an acyclic subgraph, Diskretn. Anal. Issled. Oper. Ser.1 8 (4) (2001) 34-53.
[CKW] G. Chartrand, H.V.Kronk, C.E.Wall, The point-arboricity of a graph, Israel J. Math. 6 (1968) 169-175.
[KM] H.V. Kronk, J. Mitchem, Critical point arboritic graphs, J. London Math. Soc. 9 (1974/75) 459-466.
[P] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75.
[S] S.K. Stein, B-set and planar maps, Pacific J. Math. 37 (1971) 217-224.