Maximising x(G)

Question

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

1. Any two vertices sharing an edge must have a common colour.
2. 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)$?

Answer 1

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.

Answer 2

⁩
Idk it is true or not ... We can construct a complete bipartite graph which is balanced as early as possible .

Such construction is per Tarun's construction.so maximising x(G) can be done by finding maximal triangle free vertices.

Case1 if n(even) then we can construct biparite graph with lenth $n/2$.hence this creates$n²/4$ vertices. Observation two vertices are in same Side (as they are not adjecent) we can't color any 3 points with same color .so it need distinct color . $X(G)\ge n²/4$

Case2 If n is odd then there are (n+1)(n-1)/4 vertices with partition size n+1/2 So $ x(G)>= n²-1/4$

So ,max{x(G)}= n²/4 for enen n = n²-1/4 ,for odd n