Split the integers 1 to 36 into two sets, A and B, such that any number in set A has a common divisor greater than 1 with no more than two other numbers in A, but for every number in B there are at least three numbers in A with which it has a common divisor.
How large can set A be?
In general, for which N is such a splitting of the integers 1 to N possible?
Via integer linear programming, the largest $|A|$ is
$17$, attained by $A=\{1,2,3,5,7,9,11,13,16,17,19,23,25,27,29,31,32\}$
and the smallest $|A|$ is
$14$, attained by $A=\{1,5,7,11,12,13,17,18,19,23,25,29,31,36\}$.
If B can be empty, using this strategy would get us this partition
$A$ includes 1, all prime numbers <= $N$ and largest 2 exponents for each prime <= $N$
Examples
$ N = 1, A = \{1\}$
$ N = 2, A = \{1, 2\}$
$ N = 3, A = \{1, 2, 3\}$
$ N = 4, A = \{1, 2, 3, 4\}$
$ N = 5, A = \{1, 2, 3, 4, 5\}$
$ N = 6, A = \{1, 2, 3, 4, 5\}$
$ N = 7, A = \{1, 2, 3, 4, 5, 7\}$
$ N = 8, A = \{1, 2, 3, 4, 5, 7, 8\}$
$ N = 9, A = \{1, 2, 3, 4, 5, 7, 8, 9\}$
$ N = 10, A = \{1, 2, 3, 4, 5, 7, 8, 9\}$
$ N = 11, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11\}$
$ N = 12, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11\}$
$ N = 13, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 14, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 15, A = \{1, 2, 3, 4, 5, 7, 8, 9, 11, 13\}$
$ N = 16, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16\}$
$ N = 17, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17\}$
$ N = 18, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17\}$
$ N = 19, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 20, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 21, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 22, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19\}$
$ N = 23, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23\}$
$ N = 24, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23\}$
$ N = 25, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25\}$
$ N = 26, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25\}$
$ N = 27, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27\}$
$ N = 28, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27\}$
$ N = 29, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29\}$
$ N = 30, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29\}$
$ N = 31, A = \{1, 2, 3, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31\}$
$ N = 32, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 33, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 34, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 35, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 36, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32\}$
$ N = 37, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$
$ N = 38, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$
$ N = 39, A = \{1, 2, 3, 5, 7, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37\}$
I verified this with a program for about 10**5 and it looked satisfiable.
