%I #40 Jul 30 2023 15:59:47

%S 1,1,2,3,4,5,6,7,9,10,12,14,16,18,20,22,25,27,30,33,36,39,42,45,49,52,

%T 56,60,64,68,72,76,81,85,90,95,100,105,110,115,121,126,132,138,144,

%U 150,156,162,169,175,182,189,196,203,210,217,225,232,240,248

%N Maximum product of the vertex arboricities of a graph of order n and its complement.

%C The vertex arboricity is the minimum number of sets into which the vertices of a graph G can be partitioned so that each set induces a forest.

%C The extremal graphs (for n == 1 (mod 4)) are characterized in Bickle (2023).

%D D. R. Lick and A. T. White, Point-partition numbers of complementary graphs, Math. Japonicae 19 (1974), 233-237.

%H Allan Bickle, <a href="https://doi.org/10.1016/j.disc.2023.113392">Extremal Decompositions for Nordhaus-Gaddum Theorems</a>, Discrete Math, 346 7 (2023), 113392.

%H J. Mitchem, <a href="https://doi.org/10.4153/CJM-1971-029-3">On the point-arboricity of a graph and its complement</a>, Canad. J. Math. 23 (1971), 287-292.

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,0,0,0,1,-2,1).

%F a(n) = floor(((n+3)/2)^2 / 4).

%F G.f.: (1 - x + x^2)/((1 - x)^3*(1 + x)*(1 + x^2)*(1 + x^4)). - _Stefano Spezia_, Apr 22 2023

%e A 5-cycle has vertex arboricity 2, and its complement is also a 5-cycle, so a(5) is at least 2*2 = 4.

%t LinearRecurrence[{2,-1,0,0,0,0,0,1,-2,1},{1,1,2,3,4,5,6,7,9,10},60] (* _Harvey P. Dale_, Jul 30 2023 *)

%Y Cf. A002620 (maximum product of the chromatic numbers of a graph of order n-1 and its complement).

%K nonn,easy

%O 1,3

%A _Allan Bickle_, Apr 20 2023