Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-17T20:22:44.144Z Has data issue: false hasContentIssue false

On the Point-Arboricity of a Graph and its Complement

Published online by Cambridge University Press:  20 November 2018

John Mitchem*
Affiliation:
Western Michigan University, Kalamazoo, MichiganSan Jose State College, San Jose, California
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The point-arboricity ρ (G) of a graph G is defined as the minimum number of subsets into which the point set V(G) of G may be partitioned so that each subset induces an acyclic subgraph. Equivalently, the point-arboricity of G may be defined as the least number of colours needed to colour the points of G so that no cycle of G has all of its points coloured the same. This term was introduced by Chartrand, Geller, and Hedetniemi [1], although the concept was first considered by Motzkin [4].

As with the chromatic number of a graph G, which we denote by χ(G), there is no explicit formula for the point-arboricity of a graph. However, Nordhaus and Gaddum [5] have shown that if G is a graph with p points, then

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1971