I've asked the following question on MathExchange site, with a bounty, with no answer or comments. Maybe I would have additional comments here. The problem came to be while reading some articles on finite geometry. I began wondering if anybody had previously studied this.

**Reminder on Latin Square:** Given a set $S$ of $n$ elements (we will use $[n]$ in the following for simplicity), a Latin square $L$ is a function $L : [n]\times [n] \to S$, i.e., an $n\times n$ array with elements in $S$, such that each element of $S$ appears exactly once in each row and each column. For example,

Let $L_1$ and $L_2$ be two Latin squares over the ground sets $S_1$, $S_2$ respectively. They are called ** orthogonal** if for every $(x_1, x_2) \in S_1 \times S_2$ there exists a unique $(i,j)\in [n] \times [n]$ such that $L_1(i,j) = x_1$ and $L_2(i,j) = x_2$. For example, the following are two orthogonal Latin squares of order 3.

It is known that there at most $n-1$ mutually orthogonal Latin squares of order $n$, and that the bound is achieved if and only there exist an affine plane of order $n$.

**The graph definition:** I'm building a graph $G_n$ with vertex set the Latin squares of order $n$ and two vertices are adjacent iff the Latin squares are orthogonal.

I want to understand some properties of this graph. For simplicity I consider the squares up to permutation of $[n]$, hence w.l.o.g. all my squares have for first line $\{1,2,\ldots,n\}$. Indeed if I call $H_n$ the graph not up to permutations, then $H_n$ is the $n!$ graph blowup of $G_n$, or using the Tensor product $$ H_n = G_n \times K_{n!}$$ As I'm mainly interested in the chromatic number of my graph, and we know that $\chi(H_n)\leq \min\{\chi(G_n) ; n!\}$, I will study only $G_n$.

For instance $G_2=K_1$, $G_3=K_2$.

I know that :

- It's trivial that $G_n$ is not complete.
If there exist an affine plane of order $n$ then $G_n$ contains $K_{n-1}$ as a subgraph, and $\chi(G_n)\geq n-1$.

$G_4$ is made of 2 disjoint $K_3$ and 18 isolated vertices, for a total of 24 Latin squares.

$G_5$ is made of 36 disjoint $K_4$ and 1200 isolated vertices, for a total of 1344 Latin squares.

The case $n=6$ would be the first interesting case, as there are no affine plance of order 6, hence we will find no $K_5$ in $G_6$. It is known since 1901 (from Tarry hand checking all Latin squares of order 6) that no two Latin squares of order 6 are mutually orthogonal. So $G_6$ is made of only isolated vertices (with 1,128,960 vertices).

It is also know that the case $n=2$ and $n=6$ are the only one with only isolated vertices. (see design theory by Beth, Jingnickel and Lenz).

From the article "Monogamous Latin Square by Danziger, Wanless and Webb, available on Wanless website here. The authors show that for all $n > 6$, if $n$ is not of the form $2p$ for a prime $p \geq 11$, then there exists a Latin square of order $n$ that possesses an orthogonal mate but is not in any triple of Mutually Orthogonal Latin Squares. Therefore our graph $G_n$ will have some isolated $K_2$

**I wonder the following :**

- What is the maximum degree of $G_n$ ? We know that we have at most $n-1$ mutually orthogonal latin squares, but to how many squares can one square be orthogonal (still up to permutation)?
- Do we have any other info on the chromatic number, not coming from the property $\chi(G_n)\leq \Delta+1$.
Can $G_n$ contains an induce $k$-cycle with $k>3$ (i.e. chordless cycle)?

The stronger statement would be the following conjecture

Conjecture: for any $n$, $G_n$ is the disjoint union of complete subgraphs (of different sizes).

Or said otherwise, the orthogonal relation is transitive (when restricted to our Latin squares with first row fixed at $\{1,2,\ldots,n\}$.

I would welcome any intuition, direction for some articles, or any known additional facts.