cp's OEIS Frontend

A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

%I A352208 #10 Mar 15 2022 05:22:30
%S A352208 1,1,1,4,10,20,35,56,84
%N A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.
%C A352208 This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).
%C A352208 In the following, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges.
%C A352208   a(10) >= 140 by FCB(2, 2, 2, 2, 2);
%C A352208   a(11) >= 268 by FCB(2, 2, 2, 2, 3);
%C A352208   a(12) >= 517 by FCB(2, 2, 3, 2, 3);
%C A352208   a(13) >= 911 by FCB(2, 3, 2, 3, 3);
%C A352208   a(14) >= 1515 by FCB(2, 3, 3, 3, 3);
%C A352208   a(15) >= 2525 by FCB(3, 3, 3, 3, 3).
%H A352208 Natasha Morrison and Alex Scott, <a href="http://dx.doi.org/10.1016/j.jctb.2017.03.007">Maximising the number of induced cycles in a graph</a>, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
%F A352208 a(m+n) >= a(m)*a(n).
%F A352208 Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .
%e A352208 For 3 <= n <= 9, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal (it is the unique optimal graph for 4 <= n <= 9), but a(10) >= 140 > binomial(10,3).
%Y A352208 Cf. A000292, A076315, A076322.
%Y A352208 For a list of related sequences, see cross-references in A342211.
%K A352208 nonn,more
%O A352208 1,4
%A A352208 _Pontus von Brömssen_, Mar 08 2022