Least number of vertices in a graph with which one can uniquely recover some partition of N Given a partition of an integer $N$, its $P$-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one (i.e. they are not relatively prime).
For an integer $N$, let $k(N)$ be the least number such that a graph on $k(N)>1$ vertices exists that is the P-graph of exactly one partition of $N$ into $k(N)$ parts. It has been shown, for example, that $k(200)=6$. Determining $k(N)$ in general seems hopeless, but perhaps satisfactory estimates can be found. In particular, how big is, say, $k(1000)$? Less than $12$, as estimated by this proposer?
 A: Consider a cycle of length greater than 3. If we label the edges of this P-graph by the gcd's, then a vertex on this cycle between two labels a and b must be a multiple of ab, and a and b are coprime. Thus all the labels are pairwise coprime and greater than 1, so the smallest k many such labels can be no smaller than the smallest k primes.
Suppose (going around a ten cycle) we have edge labels in order being 17 5 23 2 29 3 19 7 13 11. Then these vertices add up to at least 1000 (at least 1002, unfortunately). If there is a labelling that yields a smaller vertex sum, then augment the graph with isolated vertices. Since we are using the smallest labels, I suspect this will lead to a proof of k(1000) being less than 20, perhaps less than 12.  At least it will show k(m) is at most 10 for some m not much smaller than 1000.
Gerhard "Maybe Freddy Can Help Here" Paseman, 2018.04.27.
A: Freddy Barrera has shown that $k(1000)>5$ by verifying that every graph with fewer than 6 vertices (other than the singleton) is the P-graph of at least two partitions of 1000. On the other hand, from the following graph on 35 vertices a unique partition of 1000 can be recovered, hence $k(1000)<36$.
A: For the sake of completeness, here is the graph found by user44191 (see above), which shows that $k(1000)<11$:

A: @user44191 Based on your "cycles and tails" idea Freddy Barrera devised and checked by exhaustive computer search that from the following P-graph a unique partition of 1000 in nine parts can be recovered:

