An Analogue to the Heawood Map‐Colouring Problem

2. Definitions and preliminary results The point-arboricity p(G) of a graph G is defined (see [1]) as the minimum number of subsets into which the point set of G may be partitioned so that each subset induces an acyclic subgraph. (A subgraph H of G is induced if every line of G which joins two points of if is a line of H.) The point-arboricity may be interpreted as a " colouring number", since p(G) is the minimum number of colours needed to colour the points of G so that no cycle of G has all its points coloured the same. The point-arboricity of a surface Sn, denoted by p(Sn), is the maximum pointarboricity among all graphs which can be embedded on Sn. It was shown in [1,4] that p(S0) < 3 and the equality p(S0) = 3 was established in [2]. If v is a point in a graph G, then by G — v we mean the graph obtained by removing v and all lines incident with v. A graph G is called critical with respect to pointarboricity or simply critical if p(G — v) < p(G) for all points y of G. A k-critical graph is a critical graph G having p(G) — k. The following two properties of critical graphs are easily established [2, Prop. 1 and Prop. 2]: