On the Point-Arboricity of a Graph and its Complement

Mitchem, John

Canadian journal of mathematics, Tome 23 (1971) no. 2, pp. 287-292

Résumé

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

Détail

DOI : 10.4153/CJM-1971-029-3

Bibliographie

[1] 1. Chartrand, G., Geller, D., and Hedetniemi, S., Graphs with forbidden subgraphs, J. Combinatorial Theory (to appear). Google Scholar

[2] 2. Chartrand, G., Kronk, H. V., and Wall, C. E., The point-arboricity of a graph, Israel J. Math. 6 (1968), 169–175. Google Scholar

[3] 3. Finck, H.-J., On the chromatic number of a graph and its complement, pp. 99–113 in Theory of graphs, Proceedings of the Colloquium held at Tihany, Hungary, 1966, edited by Erdös, P. and Katona, G. (Academic Press, New York, 1968). Google Scholar

[4] 4. Motzkin, T. S., Colorings and cocolorings and determinant terms, pp. 253–254 in Theory of graphs, International Symposium on the theory of graphs held in Rome, July, 1966 (Gordon and Breach, New York, 1967). Google Scholar

[5] 5. Nordhaus, E. A. and Gaddum, J. W., On complementary graphs, Amer. Math. Monthly 63 (1956), 175–177. Google Scholar

[6] 6. Stewart, B. M., On a theorem of Nordhaus and Gaddum, J. Combinatorial Theory 6 (1969), 217–218. Google Scholar