MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 edited for clarity

As an alternative to my earlier computational answer for particular graphs G, here is a worst-case description of the asymptotic growth of the minimum size of the integers Nj 

Let h be the sum of |V(G)| and the number of maximal cliques in G (bounded above by |E(G)|, which is saturated for bipartite graphs, whose edges are the maximal cliques). Let c be the maximum number of maximal cliques to which a vertex v ∈ V(G) may belong. Because ph ≤ h (ln(h) + ln ln(h)), we can bound $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(h^c \log^c(h)\Big). $$ This bound is asymptotically saturated by placing the largest prime weights on the vertex in the largest number of maximal cliques, and those maximal cliques of which it is a part, which is obviously a bad thing to do. But e.g. in Cayley graphs G, every vertex belongs to the same number of maximal cliques, this asymptotic growth cannot be avoided, as there will exist vertices v for which Nv will consist exclusively of a product of primes pt, for t bounded below by a constant fraction of h.

One can construct bipartite Cayley graphs in which the degree of each vertex is a constant fraction of n = |V(G)|. We then have h = α n for some 0 < α < 1; and h = |V(G)| + |E(G)| ∈ O(n2), so that $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(n^{2\alpha n} \log^{\alpha n}(n)\Big) $$ for such graphs. Thus there exist graphs for which the coefficients Nj grow much more quickly than e.g. the factorial function.
show/hide this revision's text 1

As an alternative to my earlier computational answer for particular graphs G, here is a worst-case description of the asymptotic growth of the minimum size of the integers Nj 

Let h be the sum of |V(G)| and the number of maximal cliques in G (bounded above by |E(G)|, which is saturated for bipartite graphs, whose edges are the maximal cliques). Let c be the maximum number of maximal cliques to which a vertex v ∈ V(G) may belong. Because ph ≤ h (ln(h) + ln ln(h)), we can bound $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(h^c \log^c(h)\Big). $$ This bound is asymptotically saturated by placing the largest prime weights on the vertex in the largest number of maximal cliques, and those maximal cliques of which it is a part, which is obviously a bad thing to do. But e.g. in Cayley graphs G, every vertex belongs to the same number of maximal cliques, this asymptotic growth cannot be avoided, as there will exist vertices v for which Nv will consist exclusively of a product of primes pt for t a constant fraction of h.

One can construct bipartite Cayley graphs in which the degree of each vertex is a constant fraction of n = |V(G)|. We then have h = α n for some 0 < α < 1; and h = |V(G)| + |E(G)| ∈ O(n2), so that $$ \large \Big(\min_{\small\text{weightings}} \; \max_{v \in V(G)}\; N_v\Big) \;\;\in\;\; \mathrm O\Big(n^{2\alpha n} \log^{\alpha n}(n)\Big) $$ for such graphs. Thus there exist graphs for which the coefficients Nj grow much more quickly than e.g. the factorial function.