On the equitable vertex arboricity of graphs

Abstract

An equitable $(t,k)$-tree-colouring of a graph G is a t-colouring of vertices of G such that the sizes of any two colour classes differ by at most one and the subgraph induced by each colour class is a forest of maximum degree at most k. The strong equitable vertex k-arboricity, denoted by $v{a}_k^{\equiv }\left(G\right)$, is the smallest t such that G has an equitable $(t^{\prime },k)$-tree-colouring for every $t^{\prime }\ge t$. In this paper, we give upper bounds for $v{a}_1^{\equiv }\left(G\right)$ when G is a balanced complete bipartite graph $K_{n,n}$ and $n\equiv 0,1\left(mod3\right)$. For some special cases, we determine the exact values. We also prove that: (1) $v{a}_{\mathrm{\infty }}^{\equiv }\left(G\right)\le 12$ for every planar graph without 4-cycles, 5-cycles and 6-cycles; (2) $v{a}_{\mathrm{\infty }}^{\equiv }\left(G\right)\le 6$ for every planar graph with neither 3-cycles nor adjacent 4-cycles.

Keywords:

• equitable colouring
• vertex k-arboricity
• k-tree-colouring
• complete bipartite graph
• planar graph

AMS 2010 Subject Classifications:

• 05C15
• 05C78

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Project 10971025 supported by NSFC.