login
A352208
Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.
1
1, 1, 1, 4, 10, 20, 35, 56, 84
OFFSET
1,4
COMMENTS
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).
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.
a(10) >= 140 by FCB(2, 2, 2, 2, 2);
a(11) >= 268 by FCB(2, 2, 2, 2, 3);
a(12) >= 517 by FCB(2, 2, 3, 2, 3);
a(13) >= 911 by FCB(2, 3, 2, 3, 3);
a(14) >= 1515 by FCB(2, 3, 3, 3, 3);
a(15) >= 2525 by FCB(3, 3, 3, 3, 3).
LINKS
Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.
FORMULA
a(m+n) >= a(m)*a(n).
Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .
EXAMPLE
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).
CROSSREFS
For a list of related sequences, see cross-references in A342211.
Sequence in context: A374710 A347252 A201722 * A341193 A090579 A276643
KEYWORD
nonn,more
AUTHOR
STATUS
approved