Maximising x(G) Let $G$ be a graph on $n$ vertices. To each vertex, we assign zero or more colours such that


*

*Any two vertices sharing an edge must have a common colour.

*Any two vertices not sharing an edge do not share any common colours.


Let $x(G)$ be the least number of colours needed to fulfil the condition. Across all possible $G$, what's the maximum value of $x(G)$? 

I would argue that the best you can do is using a maximal triangle-free graph (per Turan's construction, this is a complete bipartite graph whose partitions are as balanced as possible). It at least serves as a lower bound: take $n$ even (for simplicity, I'll handle odd in a bit), and construct the complete bipartite graph with partitions each of size $n/2$. This creates $n^2/4$ edges, and it's quick to note that no color can be shared among 3 or more vertices, because by pigeonhole, 2 would have to be on the same side (and thus are not adjacent). So every edge needs its own color, and thus $x(G) \geq n^2/4$ for $n$ even. (With $n$ odd, instead you have $\frac{n - 1}{2}\frac{n + 1}{2} = \frac{n^2 - 1}{4}$ edges and thus colors.)
As for why this is probably best possible: the proof of Turan's theorem is the justification behind this construction being maximally triangle-free. In this scenario, each edge has its own color, but if we have a triangle, suddenly all three of those edges can share a color, that is, if we add an edge to our current construction (say our current edge goes between vertices who share color 1, and we add an edge between the vertex in the "top" partition and a new vertex up top), then suddenly the new top vertex and the original bottom vertex are allowed to share color 1 instead of having to use whatever color their edge originally induced.
Like I said, this is wishy-washy, so I would love for someone to tighten it up, but I'm fairly confident triangle-free is the way to go.
