93
Views
5
CrossRef citations to date
0
Altmetric
Original Articles

On the equitable vertex arboricity of graphs

&
Pages 844-853 | Received 13 Oct 2014, Accepted 16 Feb 2015, Published online: 27 Mar 2015
 

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 vak(G), is the smallest t such that G has an equitable (t,k)-tree-colouring for every tt. In this paper, we give upper bounds for va1(G) when G is a balanced complete bipartite graph Kn,n and n0,1(mod3). For some special cases, we determine the exact values. We also prove that: (1) va(G)12 for every planar graph without 4-cycles, 5-cycles and 6-cycles; (2) va(G)6 for every planar graph with neither 3-cycles nor adjacent 4-cycles.

AMS 2010 Subject Classifications:

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

Project 10971025 supported by NSFC.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.