\title{Orthogonal Colorings of Graphs}

\author{Yair Caro \thanks{e-mail: yairc@macam98.ac.il}\\
and\\
Raphael Yuster \thanks{e-mail: raphy@macam98.ac.il}\\
Department of Mathematics\\
University of Haifa-ORANIM, Tivon 36006, Israel.\\
{\bf AMS Subject Classification:} 05C15 (primary),\\
05B15, 05C35 (secondary).\\
\\
Submitted: February 4, 1998; Accepted: December 6, 1998
}

\date{} %Prevent the date from being printed
\documentclass[11pt]{article}
\usepackage{latexsym}

% DIMENSION OF TEXT:
\textheight 9in %Height of text excluding running head and foot.
\textwidth 6in %Width of text line.

% SIDE MARGINS:
\oddsidemargin 0pt %Left margin on odd-numbered pages.
\evensidemargin 0pt %Left margin on even-numbered pages.
\marginparwidth 40pt %Width of marginal notes.
\marginparsep 10pt %Horizontal space between outer margin and note.

% VERTICAL SPACING:
\topmargin -\headheight %Distance from top of page to running head.
\headsep 13pt %Space between running head and text.

\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{conj}[theo]{Conjecture}
\renewcommand{\baselinestretch}{1.3}
\newcommand{\ignore}[1]{}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 6 (1999), \#R5\hfill}
\thispagestyle{empty}
\begin{document}
\maketitle
\setcounter{page}{1}
\begin{abstract}

\noindent
An {\em orthogonal coloring} of a graph $G$ is a pair $\{c_1,c_2\}$ of proper
colorings of $G$, having the property that if two vertices are colored with
the same color in $c_1$, then they must have distinct colors in $c_2$. The
notion of orthogonal colorings is strongly related to the notion of
orthogonal Latin squares. The {\em orthogonal chromatic number} of $G$,
denoted by $O\chi(G)$, is the minimum possible number of colors used in an
orthogonal coloring of $G$. If $G$ has $n$ vertices, then the definition
implies that $\left\lceil \sqrt{n} \, \right\rceil \leq O\chi(G) \leq n$. $G$ is said to
have an {\em optimal} orthogonal coloring if $O\chi(G) = \left\lceil \sqrt{n} \,
\right\rceil$. If, in addition, $n$ is an integer square, then we say that $G$ has
a {\em perfect} orthogonal coloring, since for any two colors $x$ and $y$,
there is exactly one vertex colored by $x$ in $c_1$ and by $y$ in $c_2$.

The purpose of this paper is to study the parameter $O\chi(G)$ and supply
upper bounds to it which depend on other graph parameters such as the maximum
degree and the chromatic number. We also study the structure of graphs having
an optimal or perfect orthogonal coloring, and show that several classes of
graphs always have an optimal or perfect orthogonal coloring. We also
consider the {\em strong} version of orthogonal colorings, where no vertex
may receive the same color in both colorings.
\end{abstract}

\section{Introduction}
All graphs considered here are finite, undirected, and have no loops or
multiple edges. For the standard graph-theoretic and design-theoretic
notations the reader is referred to \cite{Bo} and to \cite{CoDi}. A {\em
$k$-orthogonal coloring} of a graph $G$, is a set $\{c_1, \ldots,c_k\}$ of
proper colorings of $G$, with the additional property that if $u$ and $v$ are
two distinct vertices having the same color in some coloring $c_i$, then they
must have distinct colors in all the other colorings $c_j$ where $j \neq i$.
A 2-orthogonal coloring is simply called an {\em orthogonal coloring}. The
{\em $k$-orthogonal chromatic number} of $G$, denoted by $O\chi_k(G)$, is the
minimum possible number of colors used in a $k$-orthogonal coloring of $G$.
When $k=2$ we simply define $O\chi(G)=O\chi_2(G)$, to be the {\em orthogonal
chromatic number} of $G$. Clearly, we may take $c_1$ to be a coloring which
colors every vertex by a distinct color, and $c_i=c_1$, for $i=2,\ldots,k$.
This shows that $O\chi_k(G) \leq n$, where $n$ is the number of vertices of
$G$. (Note that, trivially, $O\chi_k(G) \leq O\chi_{k+1}(G)$). On the other
hand, the definition implies that $O\chi(G) \geq \chi(G)$, and also that
$O\chi(G) \geq \left\lceil \sqrt{n} \, \right\rceil$, since otherwise, there are less than
$n$ possible color pairs. We can therefore summarize:
\begin{equation}
\label{e1}
\max\{\chi(G), \left\lceil \sqrt{n} \, \right\rceil\} \leq O\chi(G) \leq O\chi_3(G) \leq
\ldots \leq n.
\end{equation}

There are many graphs which satisfy $O\chi(G) = \left\lceil \sqrt{n} \, \right\rceil$. For
example, $O\chi(C_5)=3$ as we may color the cycle once by the colors
$(1,2,3,1,2)$ and then by the colors $(3,1,3,1,2)$. Note that we have
$O\chi(C_5)=\chi(C_5)$. These observations naturally raise the following
definitions:
\begin{enumerate}
\item
$G$ is said to have an {\em optimal} $k$-orthogonal coloring ($k$-OOC) for
short) if $O\chi_k(G)= \left\lceil \sqrt{n} \, \right\rceil$. A 2-OOC is simply called an
OOC.
\item
If $n$ is an integer square and $G$ has a $k$-OOC we say that $G$ has a {\em
perfect} $k$-orthogonal coloring ($k$-POC for short), as, in this case, each
ordered color pair appears in each ordered pair of colorings in exactly one
vertex. A $2$-POC is simply called a POC.
\end{enumerate}
An example of a graph having a POC is $C_9$, since we may color the cycle
first by\\ $(1,2,3,1,2,3,1,2,3)$ and then by $(1,2,1,2,3,2,3,1,3)$.

The notion of $k$-orthogonal colorings is strongly related to the notion of
orthogonal Latin squares. Recall that two Latin squares $L_1,L_2$ of order
$r$ are orthogonal if for any ordered pair $(s,t)$ where $1 \leq s \leq r$
and $1 \leq t \leq r$, there is exactly one position $(i,j)$ for which
$L_1(i,j)=s$ and $L_2(i,j)=t$. It is well-known that orthogonal Latin squares
exist for every $r \notin \{2,6\}$ (cf. \cite{CoDi}). A family of
$k$-orthogonal Latin squares of order $r$, is a set of $k$ Latin squares
every two of which are orthogonal. It is well-known that for every $k$, there
exists $L(k)$, such that for every $r \geq L(k)$, there exists a family of
$k$-orthogonal Latin squares of order $r$ (cf. \cite{CoDi}, and \cite{Be} who
showed that $L(k) = O(k^{14.8})$).

Given a family $F = \{L_1,\ldots, L_k\}$ of $k$-orthogonal Latin squares of
order $r$, we define the graph $U(F)$ as follows: $G$ has $r^2$ vertices,
which are denoted by the ordered pairs $(i,j)$ for $i=1,\ldots r$,
$j=1,\ldots,r$. A vertex $(i_1,j_1)$ is joined to a vertex $(i_2,j_2)$ if for
every $p=1,\ldots,k$, $L_p(i_1,j_1) \neq L_p(i_2,j_2)$. Note that $U(F)$ is
regular of degree $r^2-k(r-1)-1$. The crucial fact is that $O\chi_k(U(F)) =
r$, since we can define the colorings $\{c_1,\ldots,c_k\}$ in the obvious
way: $c_p((i,j))=L_p(i,j)$. The pairwise-orthogonality of the members of $F$,
and the definition of $U(F)$ show that this is a $k$-orthogonal coloring of
$U(F)$. Since the coloring only uses $r$ colors, and since the number of
vertices is $r^2$, we have that $O\chi_k(U(F)) = r$, and that $U(F)$ has a
$k$-POC. This discussion yields the following fact:

\noindent
{\bf FACT 1:}\, Let $k$ and $r$ be positive integers with $r \geq L(k)$. Let
$G$ be a subgraph of every graph $X$ with $r^2$ vertices where $X$ is
$r^2-k(r-1)-1$-regular, then $O\chi_k(G) \leq r$. If, in addition, $G$ has
$r^2$ vertices, then $G$ has a $k$-POC.

$U(F)$ is a graph which can be obtained from the complete graph $K_{r^2}$ be
deleting $k$ edge-disjoint $K_r$-factors, since each Latin square $L_i \in F$
eliminates one $K_r$-factor from $K_{r^2}$, where every $K_r$ in this factor
corresponds to $r$ cells having the same symbol in $L_i$. The fact that the
distinct $K_r$-factors are edge-disjoint follows from the
pairwise-orthogonality of the members of $F$. It is interesting to note that
in case $k=2$, the graph $U(F)$ (considered as an unlabeled graph) is
independent of the actual Latin squares $\{L_1,L_2\}$. This is because
whenever we delete two edge-disjoint $K_r$-factors from $K_{r^2}$, we always
get the same graph, which we denote by $U_r$. We therefore call $U_r$ the
{\em universal orthogonal graph of order $r$}. Note that $U_r$ exists for
every $r \geq 1$, although for $r=2,6$ there is no corresponding pair of
orthogonal Latin squares. For example, $U_2=2K_2$, since by deleting two
independent edges from $K_4$ we get $C_4$, and then deleting another pair of
independent edges we get $2K_2$. Now put $U_r = K_{r^2} \setminus
\{F_1,F_2\}$ where $F_1$ is the first $K_r$-factor deleted from $K_{r^2}$ and
$F_2$ is the second $K_r$ factor deleted from $K_{r^2} \setminus \{F_1\}$. We
can associate each vertex $v$ of $U_r$ with an ordered pair of integers
$(i,j)$, $1 \leq i \leq r$ and $1 \leq j \leq r$, where $i$ is the serial
number of the clique $K_r$ in $F_1$ containing $v$, and $j$ is the serial
number of the clique $K_r$ in $F_2$ containing $v$. This association shows
that for all $r$, $O\chi(U_r)=r$ and $U_r$ has a POC. Another obvious result
of this association is that every graph $G$ with $O\chi(G) \leq r$ is isomorphic to a
subgraph of $U_r$, since we may map $v \in G$ colored with $(i,j)$ to the
vertex of $U_r$ associated with the pair $(i,j)$. We can summarize this
discussion in the following statement:

\noindent
{\bf FACT 2:}\, Let $r$ be a positive integer. A graph $G$ is isomorphic to
a subgraph of
$U_r$ if and only if $O\chi(G) \leq r$. If, in addition, $G$ has $r^2$
vertices, then $G$ has a POC.

A related concept to orthogonal coloring is the notion of {\em orthogonal
edge coloring}, introduced in \cite{ArDiHa}. In this case, one requires two
proper edge colorings with the property that any two edges which receive the
same color in the first coloring, receive distinct colors in the second
coloring. For a survey of the results on orthogonal edge colorings the reader
is referred to \cite{AlHeLi}. The results on orthogonal edge coloring
naturally translate to results on orthogonal vertex coloring when one
considers line graphs. In this paper we study the parameter $O\chi_k(G)$,
with our main attention on $O\chi(G)$. In section 2 we supply several upper
bounds to $O\chi(G)$ and $O\chi_k(G)$ which depend on other graph parameters
such as the maximum degree and the chromatic number. In some cases we are
able to obtain exact results. In particular, we prove the following theorems:
\begin{theo}
\label{t11}
Let $G$ be a graph with $n$ vertices, and with maximum degree $\Delta$. Then
$$
O\chi(G) \leq \left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta.
$$
Furthermore, if $n > \Delta(\Delta+1)$ then the r.h.s. can be reduced by 1.
For $k \geq 2$ the following upper bound holds:
$$
O\chi_k(G) \leq \min \{ 2\sqrt{k-1} \max \{\Delta, \sqrt{n}\} \; , \;
(k-1)\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta\}.
$$
\end{theo}
\begin{theo}
\label{t12}
Let $G$ be a graph with $n$ vertices, and with $\chi=\chi(G)$. Then
$$
O\chi(G) \leq O\chi_3(G) \leq \chi+\sqrt{\chi}\sqrt{n}.
$$
For $k \geq 4$ we have that
$$
O\chi_k(G) < \chi L(k-2) + \chi + \sqrt{\chi}\sqrt{n}.
$$
Furthermore, for every $\chi$ and $k$ there exists $N=N(\chi,k)$ such that if
$n > N$ then $O\chi_k(G) \leq \chi+\sqrt{\chi}\sqrt{n}$.
\end{theo}
\begin{theo}
\label{t13}
Let $G$ be a complete $t$-partite graph with vertex classes of sizes
$s_1,\ldots,s_t$. Then,
$$
O\chi(G) = \sum_{i=1}^{t} \left\lceil \sqrt{s_i} \, \right\rceil - \left\lfloor m/2 \right\rfloor
$$
where $m$ is the number of vertex classes whose size $s_i$
satisfies $\left\lceil \sqrt{s_i} \, \right\rceil \left\lfloor \sqrt{s_i}
\right\rfloor \geq s_i$ but is not an integer square.
\end{theo}
Recall that a graph $G$ is {\em $d$-degenerate} if we may order the vertices
of $G$ such that every vertex has at most $d$ neighbors preceding it in the
ordering. Such an ordering is called a {\em $d$-degenerate ordering}. For
example, trees are $1$-degenerate and planar graphs are $5$-degenerate.
Obviously, $d$-degenerate graphs have a greedy coloring with $d+1$ colors.
The next theorem bounds the $k$-orthogonal chromatic number of $d$-degenerate
graphs.
\begin{theo}
\label{t14}
Let $G$ be a $d$-degenerate graph with $n$ vertices. If $t$ satisfies
$$
(t-d)^k > {k \choose 2}(n-d-1)t^{k-2}
$$
then $O\chi_k(G) \leq t$. Consequently, for $k=2$ we get
$$
O\chi(G) \leq d + \left\lceil \sqrt{n - d} \, \right\rceil.
$$
\end{theo}
In Section 3 we consider graphs having an OOC or a POC. We prove several
extensions of Facts 1 and 2, and, in particular, we show that every graph
with maximum degree which is not too large has a $k$-OOC:
\begin{theo}
\label{t15}
If $G$ is an $n$-vertex graph satisfying $n \geq L(k-2)^2$, and $\Delta(G)
\leq (\sqrt{n}-1)/(2k)$, then $G$ has a $k$-OOC. In particular, if $n$ is a
perfect square, then $G$ has a $k$-POC.
\end{theo}
(Note that for $k=2,3$ the condition $n \geq L(k-2)^2$ is vacuous, so in these
cases, Theorem \ref{t15} applies to every $n$). In section 4 we consider
strong orthogonal colorings in which no vertex is allowed to receive the same
color in both colorings. We will show the existence of a non-trivial family
of graphs which are perfect w.r.t strong orthogonality. The final section
contains some concluding remarks and open problems.

\section{Upper bounds}
In this section we prove Theorems \ref{t11}-\ref{t14} which all give upper
bounds to $O\chi(G)$ and $O\chi_k(G)$. Depending on the graph, each theorem
may give a different estimate. The first theorem supplies a useful upper
bound for graphs with a rather large chromatic number.

\noindent
{\bf Proof of Theorem \ref{t11}:}\, We shall use the result of Hajnal and
Szemer\'edi \cite{HaSz}, which states that every graph has a proper vertex
coloring with $\Delta+1$ colors, in which every color class contains at most
$\left\lceil n/(\Delta+1) \right\rceil$ vertices and at least $\left\lfloor n/(\Delta+1)
\right\rfloor$ vertices. Let $c_1$ be such a coloring of $G$. Now add to $G$ edges
between each two vertices colored the same by $c_1$. The resulting graph,
denoted by $G_1$ has maximum degree
$$
\Delta(G_1) \leq \Delta+\left\lceil \frac{n}{\Delta+1} \right\rceil -1.
$$
Let $c_2$ be a greedy coloring of $G_1$ with $\Delta(G_1)+1$ colors. The
definition of $G_1$ implies that $c_1$ and $c_2$ are orthogonal. Since the
number of colors used by $c_1$ is $\Delta+1 \leq \Delta+\left\lceil n/(\Delta+1)
\right\rceil$, it follows that
$$
O\chi(G) \leq \Delta+\left\lceil \frac{n}{\Delta+1} \right\rceil.
$$
We can improve this bound in case $n > \Delta(\Delta+1)$. We will show that
in this case, $G_1$ satisfies the conditions of the theorem of Brooks
{\cite{Bo}}. Put $x=\Delta+ \left\lceil n/(\Delta+1) \right\rceil$. We first show that
$G_1$ does not have a clique of order $x$. Assume $X$ is any set of $x$
vertices in $G_1$. There are at most $x \cdot \Delta/2$ edges of $G$ with
both endpoints in $X$. Each vertex is adjacent in $G_1$ to at most $\left\lceil
n/(\Delta+1) \right\rceil -1$ vertices to which it was not adjacent in $G$. Thus,
there are at most $x \cdot( \left\lceil n/(\Delta+1) \right\rceil -1)/2$ such edges with
both endpoints in $X$. Summing up, there are at most $x(x-1)/2$ edges in
$G_1$ with both endpoints in $X$, where the only way to achieve this number
is if $X$ is a union of $y = x/ \left\lceil n/(\Delta+1) \right\rceil$ vertex classes of
$c_1$ with size $\left\lceil n/(\Delta+1) \right\rceil$ each. Namely, if $(\Delta +
\left\lceil n/(\Delta+1) \right\rceil)/\left\lceil n/(\Delta+1) \right\rceil$ is an integer, which
imposes that $\Delta$ be a multiple of $\left\lceil n/(\Delta+1) \right\rceil$. This,
however, is impossible, since $n > \Delta(\Delta+1)$. Thus, $X$ is not a
clique. Consequently, $G_1$ does not have a clique of order $x$. Also, note
that if $\Delta > 1$ then $x > 3$, and if $\Delta=1$ the claim holds
trivially, so in any case, the Theorem of Brooks applies to $G_1$, and $G_1$
has a coloring $c_2$ with $x-1$ colors. As before, $c_1$ and $c_2$ are
orthogonal, and $c_1$ uses only $\Delta+1$ colors, which is not greater than
$x-1$. Thus,
$$
O\chi(G) \leq x-1 = \Delta+\left\lceil \frac{n}{\Delta+1} \right\rceil -1.
$$

\noindent
For $k \geq 2$ we may use a recursive application of the Hajnal and
Szemer\'edi Theorem. Instead of coloring $G_1$ using a greedy coloring, we
can color it once again using $\Delta(G_1)+1$ colors using the Hajnal and
Szemer\'edi result. Denote this coloring by $c_2$. We now define $G_2$ by
adding to $G_1$ edges between two vertices having the same color in $c_2$.
Clearly, $\Delta(G_2) \leq \left\lceil n/(\Delta(G_1)+1) \right\rceil + \Delta(G_1)-1$.
After $k-1$ applications we obtain a graph $G_{k-1}$ with $\Delta(G_{k-1})
\leq \left\lceil n/(\Delta(G_{k-2}) + 1) \right\rceil + \Delta(G_{k-2}) -1$. We may
color $G_{k-1}$ greedily using, say, $\Delta(G_{k-1})+1$ colors, and denote
the final coloring by $c_k$. The construction shows that $\{c_1,\ldots,c_k\}$
is a family of $k$-orthogonal colorings of $G$. The recurrence equation
$\Delta(G_p) \leq \left\lceil n/(\Delta(G_{p-1})+1) \right\rceil + \Delta(G_{p-1}) - 1$
for $p=1,\ldots,k-1$ (define $G=G_0$) is dominated by both $2\sqrt{p}
\Delta(G_0)=2\sqrt{p}\Delta$, assuming $\Delta \geq \sqrt{n}$, and by
$p\left\lceil n/(\Delta+1)\right\rceil + \Delta -1$. Thus,
$$
O\chi_k(G) \leq \min \{ 2\sqrt{k-1} \max \{\Delta, \sqrt{n}\} \; , \;
(k-1)\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta\}.
$$
Note that whenever $\Delta \geq k^{1/4} \sqrt{n}$ the estimate $(k-1)\left\lceil
n/(\Delta+1) \right\rceil + \Delta$ is better than the estimate $2\sqrt{k-1}
\Delta$. $\Box$

\noindent
If the chromatic number of $G$ is large (say, greater than $\sqrt{n}$), and
close to the maximum degree, then the estimate in Theorem \ref{t11} is very
good. For example, consider a graph with $\chi(G)=n^\alpha$ and
$\Delta(G)=n^{\alpha+\epsilon}$ where $\alpha > 0.5$ and $\epsilon \geq 0$ is
small. By (\ref{e1}) and by Theorem \ref{t11} we have that
$$
n^\alpha \leq O\chi(G) \leq n^{\alpha+\epsilon} + n^{1-\alpha-\epsilon} +1 =
n^{\alpha+\epsilon}(1+o(1)).
$$

Theorem \ref{t12} supplies a useful bound for graphs with a rather small
chromatic number. Before proving it, we need the following lemma:
\begin{lemma}
\label{l21}
Let $I_t$ denote the independent set of size $t$. Then,
$O\chi(I_t)=O\chi_3(I_t)=\left\lceil \sqrt{t} \, \right\rceil$, and if $k \geq 4$ then
$O\chi_k(I_t) \leq \max \{\left\lceil \sqrt{t} \, \right\rceil \; , \; L(k-2)\}$.
\end{lemma}
{\bf Proof:}\, Let $p$ be a positive integer, and let $k \geq 3$. Suppose
there exist $k-2$ orthogonal Latin squares of order $p$. We claim that
$I_{p^2}$ has a $k$-POC. Let $L_1,\ldots, L_{k-2}$ be $k-2$ orthogonal Latin
squares or order $p$. We first assign to every vertex $v$ of $I_{p^2}$ a
distinct pair of indices $(i,j)$ where $1 \leq i \leq p$ and $1 \leq j \leq
p$. We now define the $k$ orthogonal colorings $c_1,\ldots,c_k$. Assume that
$v$ is assigned the pair $(i,j)$. Then we define $c_1(v)=i$, $c_2(v)=j$ and
$c_s(v)=L_{s-2}(i,j)$ for $s=3,\ldots,k$. It is easily verified that
$c_1,\ldots,c_k$ are pairwise orthogonal.

\noindent
Trivially, $L(1)=1$, since there exists a Latin square of every positive
order. In any case, if $\left\lceil \sqrt{t} \, \right\rceil \geq L(k-2)$, then by the
proof above, $O\chi_k(I_t)= \left\lceil \sqrt{t} \, \right\rceil$, and therefore,
$O\chi_k(I_t) \leq \max \{\left\lceil \sqrt{t} \, \right\rceil \; , \; L(k-2)\}$, for every
$k \geq 3$. Since $L(1)=1$ and since $\left\lceil \sqrt{t} \, \right\rceil \leq O\chi(I_t)
\leq O\chi_3(I_t)$ we also have $O\chi(I_t)=O\chi_3(I_t)=\left\lceil \sqrt{t}
\, \right\rceil$. $\Box$

\noindent
{\bf Proof of Theorem \ref{t12}:}\, We partition the vertices of $G$ into
$\chi$ independent sets, denoted by $C_1, \ldots, C_{\chi}.$ By using
disjoint color sets for each $C_i$, $i=1,\ldots,\chi$, and by applying Lemma
\ref{l21} to each $C_i$ we obtain that for $k=2,3$
$$
O\chi_k(G) \leq \sum_{i=1}^{\chi} \left\lceil \sqrt{|C_i|} \, \right\rceil,
$$
and for $ k \geq 4$,
$$
O\chi_k(G) \leq \sum_{i=1}^{\chi} \max \{ \left\lceil \sqrt{|C_i|} \, \right\rceil \; , \;
L(k-2) \}.
$$
Since $|C_1|+ \ldots + |C_\chi| = n$, it follows by an elementary convexity
argument that the last two inequalities are maximized when all the sets have
equal size. Thus, for $k=2,3$
$$
O\chi_k(G) \leq \sum_{i=1}^{\chi} \left\lceil \sqrt{\frac{n}{\chi}} \, \right\rceil \leq
\chi+ \sqrt{\chi}\sqrt{n},
$$
and for $k \geq 4$, if $s$ denotes the number of vertex classes whose size is
less than $L(k-2)^2$ then
\begin{eqnarray*}
O\chi_k(G) \leq
  sL(k-2)+ (\chi-s)\left\lceil \sqrt{\frac{n}{\chi-s}} \, \right\rceil &\leq&
sL(k-2) + (\chi-s) + \sqrt{\chi-s} \sqrt{n}\\
 &<& \chi L(k-2) + \chi +\sqrt{\chi} \sqrt{n}.
\end{eqnarray*}
If $n$ is sufficiently large then $sL(k-2) \leq \sqrt{n}(\sqrt{\chi} -
\sqrt{\chi -s})$, and thus
$$
O\chi_k(G) \leq \chi + \sqrt{\chi}\sqrt{n}.
$$ $\Box$

Theorem \ref{t13} shows that the orthogonal chromatic number of complete
partite graphs can be computed exactly.

\noindent
{\bf Proof of Theorem \ref{t13}:}\, Let $S_1, \ldots, S_t$ denote the vertex
classes of $G$, where $|S_i|=s_i$, and the sizes of the first $m$ classes
have the property that $s_i$ is not an integer square and $\left\lceil \sqrt {s_i}
\, \right\rceil \left\lfloor \sqrt{s_i} \right\rfloor \geq s_i$. We first create an orthogonal
coloring $\{c_1,c_2\}$ with the required number of colors. For $i=m+1,
\ldots,t$ we use $\left\lceil \sqrt{s_i} \, \right\rceil$ distinct colors to color the
vertices of $S_i$ in both $c_1$ and $c_2$, while maintaining orthogonality.
This can be done since $S_i$ is an independent set. If $m$ is odd, then $S_m$
is also colored with $\left\lceil \sqrt{s_m} \, \right\rceil$ distinct colors in both $c_1$
and $c_2$. We now consider the $\left\lfloor m/2 \right\rfloor$ pairs of classes
$\{S_1,S_2\},\ldots,\{S_{2 \left\lfloor m/2 \right\rfloor-1},S_{2 \left\lfloor m/2
\right\rfloor}\}$. In coloring the vertices of each of these pairs we proceed as
follows. Assume the pair is $\{S_i,S_{i+1}\}$, and let $\{w_1,\ldots,w_z\}$
be a set of $z$ distinct colors where $z = \left\lceil \sqrt{s_i} \, \right\rceil + \left\lceil
\sqrt{s_{i+1}} \, \right\rceil -1$. Consider all the ordered pairs of colors of the
form $(w_p,w_q)$ where $1 \leq p \leq \left\lfloor \sqrt{s_i} \right\rfloor$ and $1 \leq
q \leq \left\lceil \sqrt{s_i} \, \right\rceil$. There are at least $s_i$ such pairs, so we
may color the vertices of $S_i$ with these pairs, where the first coordinate
is the color in $c_1$ and the second is the color in $c_2$. Now consider all
the ordered pairs of colors of the form $(w_p,w_q)$ where $\left\lfloor \sqrt{s_i}
\right\rfloor + 1 \leq p \leq z$ and $\left\lceil \sqrt{s_i} \, \right\rceil + 1 \leq q \leq z$.
There are at least $s_{i+1}$ such pairs, so we may color the vertices of
$S_{i+1}$ with these pairs where the first coordinate is the color in $c_1$
and the second is the color in $c_2$. Note that no vertex of $S_i$ receives
the same color as a vertex of $S_{i+1}$ in neither $c_1$ nor $c_2$. Summing
up over all the distinct sets of colors we have used at most $ \sum_{i=1}^{t}
\left\lceil \sqrt{s_i} \, \right\rceil - \left\lfloor m/2 \right\rfloor$ colors. Thus
$$
O\chi(G) \leq \sum_{i=1}^{t} \left\lceil \sqrt{s_i} \, \right\rceil - \left\lfloor m/2 \right\rfloor.
$$

\noindent
We now need to show that any orthogonal coloring requires at least this
number of colors. Let $\{c_1,c_2\}$ be an orthogonal coloring of $G$. The
colors used by $c_1$ in $S_i$ cannot be used in any $S_j$ for $j \neq i$
since $c_1$ is proper. The same holds for $c_2$. Let $a_i$ and $b_i$ denote
the number of colors used in $S_i$ by $c_1$ and $c_2$, respectively. Thus,
$c_1$ uses $a_1+ \ldots + a_t$ colors and $c_2$ uses $b_1+ \ldots + b_t$
colors. Since $c_1$ and $c_2$ are orthogonal, we know that $a_ib_i \geq s_i$
for $i=1, \ldots, t$. The overall number of colors used by the pair
$\{c_1,c_2\}$ is
$$
\max\{ \sum_{i=1}^t a_i, \sum_{i=1}^t b_i\} \geq \left\lceil \frac{\sum_{i=1}^t
(a_i+b_i)}{2} \right\rceil.
$$
Since $a_ib_i \geq s_i$, the r.h.s. of the last inequality is minimized when
$a_i+b_i=2\left\lceil \sqrt{s_i} \, \right\rceil$ if $i > m$, and when $a_i+b_i=\left\lceil
\sqrt{s_i} \, \right\rceil + \left\lfloor \sqrt{s_i} \right\rfloor = 2\left\lceil \sqrt{s_i} \, \right\rceil -
1$ if $i \leq m$. Thus,
$$
O\chi(G) \geq \left\lceil \frac{\sum_{i=1}^t 2\left\lceil \sqrt{s_i} \, \right\rceil - m}{2}
\right\rceil = \sum_{i=1}^t \left\lceil \sqrt{s_i} \, \right\rceil - \left\lfloor m/2 \right\rfloor.
$$ $\Box$

\noindent
As an example, we have that $O\chi(K_{6,6})=5$ since $6$ is not an integer
square and $2 \cdot 3 \geq 6$, so $m=2$ in this case. Note that the same
reasoning yields $O\chi(K_{5,5})=5$ and $O\chi(K_{5,4})=5$.

\noindent
{\bf Proof of Theorem \ref{t14}:}\, Consider a $d$-degenerate ordering
$\{v_1,\ldots,v_n\}$ of the vertices of $G$. We need to create a set $\{c_1,
\ldots, c_k\}$ of $k$-orthogonal colorings. We prove the theorem by coloring
the vertices one by one while maintaining orthogonality. Coloring $v_1,
\ldots, v_d$ is trivial, since we may define, say, $c_j(v_i)=i$ for all
$j=1,\ldots,k$ and $i=1,\ldots,d$. Note that $t \geq d$ so we are still
within bounds. Assume we have successfully colored $v_1, \ldots, v_{i-1}$ ($i
> d$) by using no more than $t$ colors. We now wish to color $v_i$. Let $R$
be the set of neighbors of $v_i$ in $G$ which have already been colored.
Clearly, $|R| \leq d$. Without loss of generality, we may assume $|R|=d$.
There are at most $d$ colors used in $R$ in the coloring $c_j$. Thus, there
are at least $t-d$ ways to extend $c_j$ to $v_i$ while still maintaining that
$c_j$ is a proper coloring. Overall, there are at least $(t-d)^k$ ways to
extend all the colorings to $v_i$, and still have that all the colorings are
proper. We still need to show that at least one of these extensions maintains
orthogonality. Consider a vertex $v_j$ where $j < i$ and $j \notin R$. Any
extension of the colorings to $v_i$ which satisfies that for some distinct
colorings $c_x$ and $c_y$ $c_x(v_j)=c_x(v_i)$ and $c_y(v_j)=c_y(v_i)$ is
illegal. This eliminates at most $t^{k-2}$ extensions of the colorings to
$v_i$. Since this holds for every pair of distinct colorings and for all the
$i-d-1$ vertices $v_j$ where $j <i$ and $j \notin R$, there are at most ${k
\choose 2}(i-d-1)t^{k-2}$ illegal extensions. This still leaves at least one
legal extension since $(t-d)^k > {k \choose 2}(i-d-1)t^{k-2}$.

\noindent
For $k=2$ we can solve this inequality explicitly and obtain that if $t > d +
\sqrt{n-d-1}$ then $O\chi(G) \leq t$. In particular, $O\chi(G) \leq d+1 +
\left\lfloor \sqrt{n-d-1} \right\rfloor = d + \left\lceil \sqrt{n-d} \, \right\rceil$. $\Box$

\noindent
Theorem \ref{t14} is rather tight since $O\chi(G) \geq \left\lceil \sqrt{n}
\, \right\rceil$ always. In fact, for every $d$, we can show that there exist
$d$-degenerate graphs $G$ for which $O\chi(G) = d + \left\lceil \sqrt{n - d}
\, \right\rceil$. Consider the graph $G_{n,d} = I_{n-d} * K_d$ which is defined by
taking an independent set of order $n-d$ and a clique of order $d$ and
joining every vertex of the clique with every vertex of the independent set.
It is easy to see that $G_{n,d}$ is $d$-degenerate and that
$\chi(G_{n,d})=d+1$. We claim that we cannot color $G_{n,d}$ orthogonally
with less than $d + \left\lceil \sqrt{n-d} \, \right\rceil$ colors. Consider two orthogonal
colorings $c_1$ and $c_2$ of $G_{n,d}$. Since they are orthogonal on
$I_{n-d}$, at least one of them uses $\left\lceil \sqrt{n-d} \, \right\rceil$ colors on
$I_{n-d}$, and, obviously, an additional set of $d$ colors on $K_d$.

\section{Optimal and perfect orthogonal colorings}
In this section we focus on graphs having a $k$-OOC or a $k$-POC. Clearly, if
$\chi(G) > \left\lceil \sqrt{n} \, \right\rceil$ then $G$ does not have a $k$-OOC. Hence,
there exist graphs $G$ with $\Delta(G)=\left\lceil \sqrt{n} \, \right\rceil$ which do not
have a $k$-OOC (e.g. any graph $G$ on $n$ vertices with $\Delta(G)=\left\lceil
\sqrt{n} \, \right\rceil$ having a clique on $\left\lceil \sqrt{n} \, \right\rceil+1$ vertices as a
connected component). It turns out that graphs with a somewhat lower maximum
degree, but still with $\Delta(G)=\Omega(\sqrt{n})$, always have a $k$-OOC.
This is shown in Theorem \ref{t15}:

\noindent
{\bf Proof of Theorem \ref{t15}:}\, Consider the set $V$ of the vertices of
$G$, as a set of $n$ isolated vertices. Since $n \geq L(k-2)^2$, we have, by
Lemma \ref{l21}, that $V$ has $k$-OOC. Let $c_1,\ldots,c_k$ be such a
$k$-OOC. We will now add to $V$ edges of $G$, one by one, until we obtain
$G$. Every time we add a new edge, we will modify the colorings $c_1,\ldots,
c_k$ so that they will remain proper and pairwise orthogonal. Thus, at the
end, we will have a $k$-OOC of $G$. Assume that we have already added some
edges of $G$ to $V$, and we now wish to add the next edge $e=(u,v)$. Denote
the graph after the addition of $e$ by $G^*$. Note that $G^*$ is a spanning
subgraph of $G$, and we assume that $c_1,\ldots,c_k$ is a $k$-OOC of $G^*
\setminus \{e\}$. If $c_i(v) \neq c_i(u)$ for each $i=1, \ldots,k$, then
$c_1,\ldots,c_k$ form a $k$-OOC of $G^*$. Otherwise, we will show how to find
a vertex $x$, such that by interchanging the $k$ colors of $x$ with the
corresponding $k$ colors of $v$, we still have that every coloring is proper,
and hence this modification constitutes a $k$-OOC of $G^*$. Consider the set
$Z$ of the neighbors of $v$ in $G^*$. Clearly, $|Z| \leq \Delta = \Delta(G)$.
Let $W \subset V$ be the set of vertices $w$ having, for some $i$, and some
$z \in Z$, $c_i(w)=c_i(z)$. (We allow $z=w$, so $Z \cup \{v \} \subset W$).
Since the colorings form a $k$-OOC in $G^* \setminus \{e\}$, we know that
each color appears at most $\left\lceil \sqrt{n} \, \right\rceil$ times in each coloring.
Thus, $|W| \leq k|Z| \left\lceil \sqrt{n} \, \right\rceil$. Now let $Y \subset V$ denote
the set of vertices $y$, other than $v$, which have $c_i(y)=c_i(v)$ for some
$i=1,\ldots,k$. Clearly, $|Y| \leq k(\left\lceil \sqrt{n} \, \right\rceil -1)$. Now
consider the set $Y^*$ of all the vertices of $G^*$ which have a neighbor in
$Y$. $|Y^*| \leq |Y|\Delta$. Finally, let $X = V \setminus (W \cup Y^*)$. We
first show that $X$ is not empty. This is true since
$$
|X| \geq n - |W| - |Y^*| \geq n - k|Z|\left\lceil \sqrt{n} \, \right\rceil - \Delta|Y| \geq
n - k\Delta \left\lceil \sqrt{n} \, \right\rceil - k\Delta(\left\lceil \sqrt{n} \, \right\rceil - 1) > 0
$$
where the last inequality follows from the fact that $\Delta \leq (\sqrt{n} -
1)/(2k) < n/(k(2\left\lceil \sqrt{n} \, \right\rceil -1))$. Now let $x \in X$. We can
interchange the $k$ colors given to $x$ with the $k$ corresponding colors
given to $v$, and remain with a proper coloring. This is because after the
interchange, the colorings in the neighborhood of $v$ are proper since $x
\notin W$, and the colorings in the neighborhood of $x$ are proper since $x
\notin Y^*$, and so it has no neighbor which shares the same color with the
original color of $v$, in any of the $k$ colorings. $\Box$

Theorem \ref{t14} and (\ref{e1}) show that for every $n$-vertex tree $T$,
$\left\lceil \sqrt{n} \, \right\rceil \leq O\chi(T) \leq 1 + \left\lceil \sqrt{n-1} \, \right\rceil$.
Thus, $O\chi(T)$ is one of two consecutive possible values, and if $n-1$ is
an integer square, those upper and lower bounds coincide, so in this case,
$T$ has an OOC. In case $n-1$ is not an integer square, the example after
Theorem \ref{t14} shows that the star on $n$ vertices, $K_{1,n-1}$, has
$O\chi(K_{1,n-1})=1+ \left\lceil \sqrt{n-1} \, \right\rceil$, and thus, $K_{1,n-1}$ does
not have an OOC. However, stars are not the only examples of trees which do
not have an OOC. In fact, every tree with $n$ vertices, having a vertex of
degree $(\left\lfloor \sqrt{n-1} \right\rfloor)^2+1$ does not have an OOC. For example,
all the trees with $18 \leq n \leq 25$ vertices which have a vertex of degree
17 do not have an OOC since they contain $K_{1,17}$ and $O\chi(K_{1,17})=6$.
It is, however, an easy exercise to establish that when $n-2$ is an integer
square, and $T$ is a tree with $n$ vertices which is not a star, then $T$ has
an OOC.

\noindent
There are trees with a much lower maximal degree which do not have an OOC.
Let $n$ be an integer square, and assume (although this is not necessary)
that $n$ is even. Let $T$ be the double star obtained by joining two
$K_{1,n/2-1}$ at the roots. $T$ has maximum degree $n/2$, and we claim that
$T$ does not have an OOC whenever $(\left\lceil \sqrt{n} \, \right\rceil)(\left\lceil \sqrt{n} -
1 \right\rceil) < n$. Let $c_1$ and $c_2$ be two orthogonal colorings using $x$
colors. The roots must have distinct colors in $c_1$, denote these colors by
$1$ and $2$. At most $x-2$ leaves may have color $1$ (otherwise $c_2$ must
use $x+1$ colors if it is to be proper), and similarly, at most $x-2$ leaves
may have color $2$. Consequently, there are at least $n-2-2(x-2)=n+2-2x$
leaves that have colors other than $1$ or $2$ in $c_1$. No other color may
appear $x$ times at a leaf, so the number of other colors is at least
$(n+2-2x)/(x-1)$ So we must have $(n+2-2x)/(x-1)+2 \leq x$. Consequently,
$x(x-1) \geq n$. Thus, whenever $(\left\lceil \sqrt{n} \, \right\rceil)(\left\lceil \sqrt{n} - 1
\right\rceil) < n$, we must have $x > \left\lceil \sqrt{n} \, \right\rceil$.

\section{Strong orthogonal colorings}
A $k$-strong orthogonal coloring, is a $k$-orthogonal coloring
$c_1,\ldots,c_k$, where for each vertex $v$ and for every pair of distinct
colorings $c_i$ and $c_j$, $c_i(v) \neq c_j(v)$. The analogous definitions of
$SO\chi_k(G)$ and $SO\chi(G)$ are obvious. A graph $G$ is said to have a {\em
strong perfect orthogonal coloring} (SPOC for short) if it has $r(r-1)$
vertices and $SO\chi(G)=r$. A graph $G$ with $r^2$ vertices is said to have a
{\em strong orthogonal scheme} if it has a strong orthogonal coloring with
$r+1$ colors, where the first coloring only uses $r$ colors (thus, all
possible $r^2$ pairs of colors, under this restriction, are used).

If $G$ has $n$ vertices, then, clearly, $SO\chi(G) \geq (1 + \sqrt{1 +
4n})/2$, and $O\chi(G) \geq \sqrt{n}$. It is therefore plausible to
conjecture that $O\chi(G) \leq SO\chi(G) \leq O\chi(G)+1$. This, however, is
far from being true, as $O\chi(U_4)=4$ while it is not difficult to check
that $SO\chi(U_4)=6$. In fact, it can be shown that $SO\chi(U_r)- O\chi(U_r)$
grows linearly with $r$. It is possible, however, to prove that $SO\chi(G)
\leq O\chi(G) + \left\lceil \chi(G)/2 \right\rceil$. To see this, assume $c_1,c_2$ is an
orthogonal coloring of $G$ with $O\chi(G)$ colors (assume the colors are
$1,\ldots, O\chi(G)$). Let $X$ be the set of vertices of $G$ colored the same
in $c_1$ and $c_2$. $X$, being a subgraph of $G$, can be partitioned into at
most $\chi(G)$ independent sets $X_1,\ldots,X_{\chi(G)}$. Now, for every $v
\in X_i$ with $i \leq \chi(G)/2$ we redefine $c_1(v)=O\chi(G)+i$. For every
$v \in X_i$ with $i > \chi(G)/2$ we redefine $c_2(v)=O\chi(G)+i-\left\lfloor
\chi(G)/2 \right\rfloor$. After these modifications, $c_1,c_2$ is a strong
orthogonal coloring of $G$ using at most $O\chi(G)+\left\lceil \chi(G)/2 \right\rceil$
colors. Note that, in particular, every bipartite graph has $SO\chi(G) \leq
O\chi(G)+1$, and, by Theorem \ref{t14}, every $d$-degenerate graph has
$SO\chi(G) \leq \left\lceil (3d+1)/2 \right\rceil + \left\lceil \sqrt{n-d} \, \right\rceil$.

There exist universal graphs w.r.t. strong orthogonality and strong
orthogonal schemes. In the first case, one may take the set of all $r(r-1)$
ordered pairs $(i,j)$ where $i \neq j$ and $1 \leq i \leq r$, $1 \leq j \leq
r$ as the vertices, and connect a pair $(i,j)$ to a pair $(k,l)$ with an edge
if and only if $i \neq k$ and $j \neq l$. The resulting graph, denoted by
$W_r$, has $SO\chi(W_r)=r$, and therefore has a SPOC. Also, any graph $G$
having $SO\chi(G) \leq r$ is isomorphic to a subgraph of $W_r$, as can be seen from the
obvious isomorphism, where $v \in G$ is mapped to the vertex
$(c_1(v),c_2(v))$ of $W_r$, $c_1,c_2$ being a strong orthogonal coloring of
$G$ with at most $r$ colors. The universal graph w.r.t strong orthogonal
schemes, denoted by $X_r$. is defined analogously, where now the set of
vertices consists of all the ordered pairs $(i,j)$ where $1 \leq i \leq r$
and $1 \leq j \leq r+1$, and $i \neq j$.

All the theorems proved in Section 2 and Section 3 have analogous versions
when strong orthogonality is required, where only minor modifications are
needed. We will therefore not prove them here. We will, however, show that an
interesting family of graphs, namely the family of the complement graphs of
$U_r$, denoted by $U_r^c$, has a strong orthogonal scheme, with the exception
of $r \in \{2,3,6\}$. In other words, $U_r^c$ is a spanning subgraph of
$X_r$, unless $r \in \{2,3,6\}$. In fact we will show something more general:

\noindent
Consider the grid graph $G_{a,b}$, where $a \geq b$ are positive integers.
The vertices of $G_{a,b}$ are defined by all pairs of ordered integers
$(i,j)$ where $1 \leq i \leq a$ and $1 \leq j \leq b$, and a vertex $(i,j)$
is connected to a vertex $(k,l)$ if $i=k$ or $j=l$. Clearly, $G_{a,b}$ has
$ab$ vertices and is regular of degree $a+b-2$. Also, $G_{a,b}$ has a maximum
clique of order $a$. Clearly, $G_{r,r} = U_r^c$.

\begin{theo}
\label{t41}
$\;$
\begin{enumerate}
\item
Every subgraph $G$ of $G_{r,r-1}$ has $SO\chi(G) \leq r$. In particular,
every spanning subgraph of $G_{r,r-1}$ has a SPOC.
\item
For every positive integer $r \notin \{2,3,6\}$, every spanning subgraph of
$G_{r,r}$ has a strong orthogonal scheme.
\end{enumerate}
\end{theo}
{\bf Proof:}\, We begin with the proof of the first part. It suffices to show
that $G_{r,r-1}$ has a SPOC. We define two colorings $c_1$ and $c_2$ of
$G_{r,r-1}$ as follows. Both colorings will only use the colors
$0,\ldots,r-1$. Consider first the case where $r$ is odd. We define
$c_1((i,j))=(i+j-2) \bmod r$. Next, we define $c_2((i,j)) = (c_1(i,j) + j)
\bmod r$. Now, $c_1$ is a proper coloring since $c_1((i,j)) \neq c_1((i,k))$
when $k \neq j$, and $c_1((i,j)) \neq c_1((k,j))$ when $k \neq i$. Similar
reasoning shows that $c_2$ is proper (we use the fact that $r$ is odd). No
vertex uses the same color in both $c_1$ and $c_2$, since $1 \leq j \leq
r-1$. Finally, both colorings are orthogonal since if, for two distinct
vertices, $c_1((i,j))=c_1((k,l))$ then we must have $j \neq l$, and therefore
$c_2((i,j)) \neq c_2((k,l))$. Now assume that $r$ is even. We define
$c_1((i,j))= (i+j-2) \bmod r$ for all $1 \leq i \leq r$ and for all $1 \leq j
\leq r/2$, and we define $c_1((i,j))=(i+j-1) \bmod r$ for all $1 \leq i \leq
r$ and $r/2+1 \leq j \leq r-1$. We define $c_2((i,j))= (c_1(i,j)+j) \bmod r$
for all $i$ and $j$. Once again, it is easy to check that $c_1$ and $c_2$ are
both proper, orthogonal, and no vertex has the same color in both $c_1$ and
$c_2$.

\noindent
For the second part of the proof, it suffices to show that $G_{r,r}$ has a
strong orthogonal scheme. The proof of this relies on the existence of
self-orthogonal Latin squares for every order $r \notin {2,3,6}$
\cite{BrCoHo}. A Latin square $L$ is called self-orthogonal if the Latin
square $L^t$ (the transpose of $L$) is orthogonal to $L$. Let, therefore, $L$
be a self-orthogonal Latin square of order $r$. We define a strong orthogonal
scheme $c_1,c_2$ of $G_{r,r}$ as follows. $c_1((i,j))=L(i,j)$ for every $1
\leq i \leq r$ and $1 \leq j \leq r$. If $i \neq j$ we define $c_2((i,j)) =
L^t(i,j)=L(j,i)$. Finally, we define $c_2((i,i))=r+1$, for $i=1,\ldots,r$.
Clearly, $c_1$ is a proper coloring of $G_{r,r}$ since $L$ is a Latin square.
Also, $c_2$ is a proper coloring of $G_{r,r}$ since $L^t$ is a Latin square
and since $\{(1,1),\ldots,(r,r)\}$ are an independent set in $G_{r,r}$. Also,
the colorings are orthogonal since $L$ and $L^t$ are orthogonal and since any
two vertices of the set $\{(1,1),\ldots,(r,r)\}$ do not have the same color
in $c_1$ as the diagonal of $L$ and $L^t$ is the same, and they are
orthogonal, which implies that no symbol may appear twice in the diagonal.
Finally, $c_1$ and $c_2$ are strong orthogonal since no vertex has the same
color in both $c_1$ and $c_2$. Since $c_1$ uses only $r$ colors, the result
follows. $\Box$

\noindent
In the cases $r=2$ or $r=3$ it is easy to check that $G_{2,2}$ and $G_{3,3}$
do not have a strong orthogonal scheme. The fact that there is no strong
orthogonal scheme for $G_{6,6}$ is less trivial, and relies on the fact that
there are no two orthogonal Latin squares for $r=6$. (It is also possible to
check this by computer since one only needs to check that $W_6$ does not
contain $G_{6,6}$. A very small fraction of the 36! possible mappings need to
be checked since there are many equivalences and restrictions, which result
from the large automorphism group of $G_{6,6}$). $\Box$

\section{Concluding remarks and open problems}
\begin{enumerate}
\item
Theorem \ref{t15} shows, in particular, that if $\Delta(G) \leq
(\sqrt{n}-1)/4$, then $G$ has an OOC. It is interesting to find out if the
bound $(\sqrt{n}-1)/4$ can be improved to a bound of the form $\sqrt{n}/c$
where $c < 4$. Clearly we cannot expect $c \leq 1$, as shown in the
discussion prior to the proof of Theorem \ref{t15}. The obvious
generalization for $k > 2$ (i.e. replacing the denominator $2k$ with
something smaller) may also be considered.
\item
Determining if a graph $G$ has a POC is equivalent, according to FACT 2, to a
spanning subgraph isomorphism problem, namely, is a given graph $G$ with
$r^2$ vertices isomorphic to a spanning subgraph of $U_r$. Since general spanning subgraph
isomorphism problems are known to be NP-Complete, it is safe to conjecture
that determining if an input graph $G$ has a POC is NP-Complete. Determining
$O\chi(T)$ for a given tree $T$ with $n$ vertices is, on the other hand, a
much more interesting problem, since, as shown in Section 3, this number is
either $\left\lceil \sqrt{n} \, \right\rceil$ or $1 + \left\lceil \sqrt{n-1} \, \right\rceil$. For some
trees the answer is known (see section 3), while for a general input tree
$T$, we do not yet have an algorithm that determines, in polynomial time,
which of the two values is the right one for $T$.
\item
Is it true that every tree with maximum degree smaller than $n/2$ has an OOC?
In section 3 we have shown that there are trees with degree $n/2$ which do
not have an OOC.
\item
It would be interesting to determine the exact relationship between
$O\chi(G)$ and $SO\chi(G)$.
\item
A graph $G$ is called {\em $[n,k,r]$-partite} if the vertex set of $G$ can be
partitioned into $n$ independent sets (called vertex classes), each of size
$k$ exactly, and there are exactly $r$ independent edges between any two
vertex classes. (See \cite{Yu} which focuses on these graphs). For example,
$K_n$ is $[n,1,1]$-partite, and $C_9$ is $[3,3,3]$-partite. An {\em
independent covering} of an $[n,k,r]$-partite graph is a set of $k$
vertex-disjoint independent sets of size $n$, each containing exactly one
vertex from each vertex class. It is shown in \cite{Yu} that every
$[k,k,2]$-partite graph has an independent covering. This implies that every
$[k,k,2]$-partite graph has a POC, since one can define the first coloring
according to the vertex classes, and the second coloring according to the
independent coverings. It is not even known whether every $[k,k,3]$-graph has
an independent covering, although much more is conjectured, namely that every
$[k,k,k]$-partite graph has an independent covering (\cite{Yu} Conjecture
1.5). A seemingly easier conjecture is the following: ``Does every
$[k,k,k]$-partite graph have a POC?''
\end{enumerate}

\begin{thebibliography}{99}

\bibitem{AlHeLi} B. Alspach, K. Heinrich and G. Liu,
{\em Orthogonal factorizations of graphs}, in: {\em Contemporary Design
Theory: A collection of surveys}, (J.H. Dinitz and D.R. Stinson eds.), Wiley,
1992, 13-38.

\bibitem{ArDiHa} D. Archdeacon, J.H. Dinitz and F. Harary,
{\em Orthogonal edge colorings of graphs}, Congressus Numerantium 47 (1985),
49-67.

\bibitem{Be} T. Beth,
{\em Eine Bemerkung zur Absch\"atzung der Anzahl orthogonaler lateinischer
Quadrate mittels Siebverfahren}, Abh. Math. Sem. Univ. Hamburg 53 (1983),
284-288.
\bibitem{Bo} B. Bollob\'as,
{\em Extremal Graph Theory}, Academic Press, 1978.

\bibitem{BrCoHo} R.K. Brayton, D. Coppersmith and A.J. Hoffman,
{\em Self-orthogonal Latin squares}, Coll. Int. Th. Comb., Rome (1973), {\em
Atti del Convegni Lincei} No. 17 (1976) 509-517.

\bibitem{CoDi} C.J. Colbourn and J.H. Dinitz,
{\em CRC Handbook of Combinatorial Design}, CRC press 1996.

\bibitem{HaSz} A. Hajnal and E. Szemer\'edi,
{\em Proof of a conjecture of Erd\"os}, in: {\em Combinatorial Theory and its
Applications}, Vol. II (P. Erd\"os, A. Renyi and V. T. S\'os eds.), Colloq.
Math. Soc. J. Bolyai 4, North Holland, Amsterdam 1970, 601-623.

\bibitem{Yu} R. Yuster,
{\em Independent transversals and independent coverings in sparse partite
graphs}, Combinatorics, Probability and Computing 6 (1997), 115-125.

\end{thebibliography}
\end{document}