I've been working through a proof for a while now, and I've come across this class of graphs as the output of the algorithm I'm analyzing, however, I've managed to get absolutely nowhere proving any additional properties about them.
If you have a finite $k$-partite graph $G$, where the endpoints of each edge share a neighbor in each of the remaining independent sets, are there any other interesting properties which $G$ might have i.e. chordal, perfect...?
I'd really really appreciate any and all help on this!
Edit: The maximum cardinality of each independent set is 3 and the ultimate goal is to prove that if $G$ has this global edge property, then $G$ is guaranteed to have at least 1 $k$-clique (or that finding the clique-number of $G$ has polynomial time complexity)
Edit 2: I've posted this question here on Reddit with a description of the mentioned algorithm
The conjecture that every such graph contains a $k$-clique is false.
To see this, consider (for $k\ge 4$) a $k$-partite graph in which the $i^{\text{th}}$ part contains $3$ vertices $v_{i,1}, v_{i,2}, \dots, v_{i,3}$, and in which two vertices $v_{i,j}$ and $v_{i',j'}$ are adjacent whenever $i \ne i'$ and $j \ne j'$.
In other words, the tensor product $K_k \times K_{3}$.
For example, here is the $k=4$ case of such a graph:
In this graph, two vertices $v_{i,j}$ and $v_{i',j'}$ in different parts, whether or not they're adjacent, have a common neighbor in each other part. The $i''^{\text{th}}$ part contains a vertex $v_{i'',j}$ not adjacent to $v_{i,j}$, and a vertex $v_{i'',j'}$ not adjacent to $v_{i',j'}$, but the third vertex in that part is adjacent to both.
However, for $k\ge 4$, there is no $k$-clique in this graph - not even a $4$-clique - because if we take any $4$ vertices from this graph, two of them will agree on their second index by the pigeonhole principle. Then there's no edge between them.