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

%I #10 Mar 15 2022 05:22:30

%S 1,1,1,4,10,20,35,56,84

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

%C 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 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 a(10) >= 140 by FCB(2, 2, 2, 2, 2);

%C a(11) >= 268 by FCB(2, 2, 2, 2, 3);

%C a(12) >= 517 by FCB(2, 2, 3, 2, 3);

%C a(13) >= 911 by FCB(2, 3, 2, 3, 3);

%C a(14) >= 1515 by FCB(2, 3, 3, 3, 3);

%C a(15) >= 2525 by FCB(3, 3, 3, 3, 3).

%H 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 a(m+n) >= a(m)*a(n).

%F Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .

%e 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 Cf. A000292, A076315, A076322.

%Y For a list of related sequences, see cross-references in A342211.

%K nonn,more

%O 1,4

%A _Pontus von Brömssen_, Mar 08 2022