Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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