Orthogonal Colorings of Graphs

Yair Caro ^{∗} and Raphael Yuster ^{†} Department of Mathematics University of Haifa-ORANIM, Tivon 36006, Israel. AMS Subject Classification: 05C15 (primary), 05B15, 05C35 (secondary).

Submitted: February 4, 1998; Accepted: December 6, 1998

Abstract

An 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 orthogonal chromatic number of G, denoted by Oχ(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 ⌈\sqrt{n} ⌉ ≤ Oχ(G) ≤ n. G is said to have an optimal orthogonal coloring if Oχ(G) = ⌈\sqrt{n} ⌉. If, in addition, n is an integer square, then we say that G has a 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χ(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 strong version of orthogonal colorings, where no vertex may receive the same color in both colorings.

1 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 [4] and the electronic journal of combinatorics 6 (1999), #R5 2

∗e-mail: yairc@macam98.ac.il †e-mail: raphy@macam98.ac.il

to [6]. A k-orthogonal coloring of a graph G, is a set {c_{1}, …, 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 ≠ i. A 2-orthogonal coloring is simply called an orthogonal coloring. The k-orthogonal chromatic number of G, denoted by Oχ_{k}(G), is the minimum possible number of colors used in a k-orthogonal coloring of G. When k = 2 we simply define Oχ(G) = Oχ_{2}(G), to be the 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, …, k. This shows that Oχ_{k}(G) ≤ n, where n is the number of vertices of G. (Note that, trivially, Oχ_{k}(G) ≤ Oχ_{k+1}(G)). On the other hand, the definition implies that Oχ(G) ≥ χ(G), and also that Oχ(G) ≥ ⌈\sqrt{n} ⌉, since otherwise, there are less than n possible color pairs. We can therefore summarize:

max\{χ(G), ⌈\sqrt{n} ⌉\} ≤ Oχ(G) ≤ Oχ_{3}(G) ≤ … ≤ n.  (1)

There are many graphs which satisfy Oχ(G) = ⌈\sqrt{n} ⌉. For example, Oχ(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χ(C_{5}) = χ(C_{5}). These observations naturally raise the following definitions:

1. G is said to have an optimal k-orthogonal coloring (k-OOC) for short) if Oχ_{k}(G) = ⌈\sqrt{n} ⌉. A 2-OOC is simply called an OOC.

2. If n is an integer square and G has a k-OOC we say that G has a 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.

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 ≤ s ≤ r and 1 ≤ t ≤ 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 ∉ {2, 6} (cf. [6]). 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 ≥ L(k), there exists a family of k-orthogonal Latin squares of order r (cf. [6], and [3] who showed that L(k) = O(k^{14.8})).

Given a family F = {L_{1}, …, 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, … r, j = 1, …, r. A vertex (i_{1}, j_{1}) is joined to a vertex (i_{2}, j_{2}) if for every p = 1, …, k, L_{p}(i_{1}, j_{1}) ≠ L_{p}(i_{2}, j_{2}). Note that U(F) is regular of degree r^{2} − k(r − 1) − 1. the electronic journal of combinatorics 6 (1999), #R5 3

The crucial fact is that Oχ_{k}(U(F)) = r, since we can define the colorings {c_{1}, …, 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χ_{k}(U(F)) = r, and that U(F) has a k-POC. This discussion yields the following fact: FACT 1: Let k and r be positive integers with r ≥ 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χ_{k}(G) ≤ 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} ∈ 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 universal orthogonal graph of order r. Note that U_{r} exists for every r ≥ 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}} \ {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}} \ {F_{1}}. We can associate each vertex v of U_{r} with an ordered pair of integers (i, j), 1 ≤ i ≤ r and 1 ≤ j ≤ 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χ(U_{r}) = r and U_{r} has a POC. Another obvious result of this association is that every graph G with Oχ(G) ≤ r is isomorphic to a subgraph of U_{r}, since we may map v ∈ 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: FACT 2: Let r be a positive integer. A graph G is isomorphic to a subgraph of U_{r} if and only if Oχ(G) ≤ r. If, in addition, G has r^{2} vertices, then G has a POC.

A related concept to orthogonal coloring is the notion of orthogonal edge coloring, introduced in [2]. 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 [1]. 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χ_{k}(G), with our main attention on Oχ(G). In section 2 we supply several upper bounds to Oχ(G) and Oχ_{k}(G) which depend on other graph parameters such as the the electronic journal of combinatorics 6 (1999), #R5 4

maximum degree and the chromatic number. In some cases we are able to obtain exact results. In particular, we prove the following theorems:

Theorem 1.1 Let G be a graph with n vertices, and with maximum degree Δ. Then

Oχ(G) ≤ ⌈\frac{n}{Δ + 1}⌉ + Δ.

Furthermore, if n > Δ(Δ + 1) then the r.h.s. can be reduced by 1. For k ≥ 2 the following upper bound holds:

Oχ_{k}(G) ≤ min\{2\sqrt{k − 1} max\{Δ, \sqrt{n}\} , (k − 1) ⌈\frac{n}{Δ + 1}⌉ + Δ\}.

Theorem 1.2 Let G be a graph with n vertices, and with χ = χ(G). Then

Oχ(G) ≤ Oχ_{3}(G) ≤ χ + \sqrt{χ}\sqrt{n}.

For k ≥ 4 we have that

Oχ_{k}(G) < χL(k − 2) + χ + \sqrt{χ}\sqrt{n}.

Furthermore, for every χ and k there exists N = N(χ, k) such that if n > N then Oχ_{k}(G) ≤ χ + \sqrt{χ}\sqrt{n}.

Theorem 1.3 Let G be a complete t-partite graph with vertex classes of sizes s_{1}, …, s_{t}. Then,

Oχ(G) = ∑_{i=1}^{t} ⌈\sqrt{s_{i}} ⌉ − ⌊m/2⌋

where m is the number of vertex classes whose size s_{i} satisfies ⌈\sqrt{s_{i}} ⌉ ⌊\sqrt{s_{i}}⌋ ≥ s_{i} but is not an integer square.

Recall that a graph G is 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 d-degenerate ordering. For example, trees are 1-degenerate and planar graphs are 5degenerate. 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.

Theorem 1.4 Let G be a d-degenerate graph with n vertices. If t satisfies

(t − d)^{k} > \binom{k}{2}(n − d − 1)t^{k−2}

then Oχ_{k}(G) ≤ t. Consequently, for k = 2 we get

Oχ(G) ≤ d + ⌈\sqrt{n − d} ⌉ .

the electronic journal of combinatorics 6 (1999), #R5 5

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:

Theorem 1.5 If G is an n-vertex graph satisfying n ≥ L(k − 2)^{2}, and Δ(G) ≤ (\sqrt{n} − 1)/(2k), then G has a k-OOC. In particular, if n is a perfect square, then G has a k-POC.

(Note that for k = 2, 3 the condition n ≥ L(k − 2)^{2} is vacuous, so in these cases, Theorem 1.5 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.

2 Upper bounds

In this section we prove Theorems 1.1-1.4 which all give upper bounds to Oχ(G) and Oχ_{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. Proof of Theorem 1.1: We shall use the result of Hajnal and Szemerédi [7], which states that every graph has a proper vertex coloring with Δ + 1 colors, in which every color class contains at most ⌈n/(Δ + 1)⌉ vertices and at least ⌊n/(Δ + 1)⌋ 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

Δ(G_{1}) ≤ Δ + ⌈\frac{n}{Δ + 1}⌉ − 1.

Let c_{2} be a greedy coloring of G_{1} with Δ(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 Δ+1 ≤ Δ+⌈n/(Δ + 1)⌉, it follows that

Oχ(G) ≤ Δ + ⌈\frac{n}{Δ + 1}⌉ .

We can improve this bound in case n > Δ(Δ + 1). We will show that in this case, G_{1} satisfies the conditions of the theorem of Brooks [4]. Put x = Δ + ⌈n/(Δ + 1)⌉. 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 · Δ/2 edges of G with both endpoints in X. Each vertex is adjacent in G_{1} to at most ⌈n/(Δ + 1)⌉ − 1 vertices to which it was not adjacent in G. Thus, there are at most x · (⌈n/(Δ + 1)⌉ − 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/ ⌈n/(Δ + 1)⌉ vertex classes of c_{1} with size ⌈n/(Δ + 1)⌉ each. Namely, if (Δ + ⌈n/(Δ + 1)⌉)/ ⌈n/(Δ + 1)⌉ is an integer, which imposes the electronic journal of combinatorics 6 (1999), #R5 6

that Δ be a multiple of ⌈n/(Δ + 1)⌉. This, however, is impossible, since n > Δ(Δ + 1). Thus, X is not a clique. Consequently, G_{1} does not have a clique of order x. Also, note that if Δ > 1 then x > 3, and if Δ = 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 Δ + 1 colors, which is not greater than x − 1. Thus,

Oχ(G) ≤ x − 1 = Δ + ⌈\frac{n}{Δ + 1}⌉ − 1.

For k ≥ 2 we may use a recursive application of the Hajnal and Szemerédi Theorem. Instead of coloring G_{1} using a greedy coloring, we can color it once again using Δ(G_{1}) + 1 colors using the Hajnal and Szemerédi 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, Δ(G_{2}) ≤ ⌈n/(Δ(G_{1}) + 1)⌉ + Δ(G_{1}) − 1. After k − 1 applications we obtain a graph G_{k−1} with Δ(G_{k−1}) ≤ ⌈n/(Δ(G_{k−2}) + 1)⌉ + Δ(G_{k−2}) − 1. We may color G_{k−1} greedily using, say, Δ(G_{k−1}) + 1 colors, and denote the final coloring by c_{k}. The construction shows that {c_{1}, …, c_{k}} is a family of k-orthogonal colorings of G. The recurrence equation Δ(G_{p}) ≤ ⌈n/(Δ(G_{p−1}) + 1)⌉ + Δ(G_{p−1}) − 1 for p = 1, …, k − 1 (define G = G_{0}) is dominated by both 2\sqrt{p}Δ(G_{0}) = 2\sqrt{p}Δ, assuming Δ ≥ \sqrt{n}, and by p ⌈n/(Δ + 1)⌉ + Δ − 1. Thus,

Oχ_{k}(G) ≤ min\{2\sqrt{k − 1} max\{Δ, \sqrt{n}\} , (k − 1) ⌈\frac{n}{Δ + 1}⌉ + Δ\}.

Note that whenever Δ ≥ k^{1/4}\sqrt{n} the estimate (k − 1) ⌈n/(Δ + 1)⌉ + Δ is better than the estimate 2\sqrt{k − 1}Δ. □ If the chromatic number of G is large (say, greater than \sqrt{n}), and close to the maximum degree, then the estimate in Theorem 1.1 is very good. For example, consider a graph with χ(G) = n^{α} and Δ(G) = n^{α+ϵ} where α > 0.5 and ϵ ≥ 0 is small. By (1) and by Theorem 1.1 we have that

n^{α} ≤ Oχ(G) ≤ n^{α+ϵ} + n^{1−α−ϵ} + 1 = n^{α+ϵ}(1 + o(1)).

Theorem 1.2 supplies a useful bound for graphs with a rather small chromatic number. Before proving it, we need the following lemma:

Lemma 2.1 Let I_{t} denote the independent set of size t. Then, Oχ(I_{t}) = Oχ_{3}(I_{t}) = ⌈\sqrt{t} ⌉, and if k ≥ 4 then Oχ_{k}(I_{t}) ≤ max\{⌈\sqrt{t} ⌉ , L(k − 2)\}.

Proof: Let p be a positive integer, and let k ≥ 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}, …, 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 ≤ i ≤ p and 1 ≤ j ≤ p. We now define the k orthogonal colorings the electronic journal of combinatorics 6 (1999), #R5 7

c_{1}, …, 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, …, k. It is easily verified that c_{1}, …, c_{k} are pairwise orthogonal. Trivially, L(1) = 1, since there exists a Latin square of every positive order. In any case, if ⌈\sqrt{t} ⌉ ≥ L(k − 2), then by the proof above, Oχ_{k}(I_{t}) = ⌈\sqrt{t} ⌉, and therefore, Oχ_{k}(I_{t}) ≤ max\{⌈\sqrt{t} ⌉ , L(k−2)\}, for every k ≥ 3. Since L(1) = 1 and since ⌈\sqrt{t} ⌉ ≤ Oχ(I_{t}) ≤ Oχ_{3}(I_{t}) we also have Oχ(I_{t}) = Oχ_{3}(I_{t}) = ⌈\sqrt{t} ⌉. □ Proof of Theorem 1.2: We partition the vertices of G into χ independent sets, denoted by C_{1}, …, C_{χ}. By using disjoint color sets for each C_{i}, i = 1, …, χ, and by applying Lemma 2.1 to each C_{i} we obtain that for k = 2, 3

Oχ_{k}(G) ≤ ∑_{i=1}^{χ} ⌈\sqrt{|C_{i}|} ⌉ ,

and for k ≥ 4,

Oχ_{k}(G) ≤ ∑_{i=1}^{χ} max\{⌈\sqrt{|C_{i}|} ⌉ , L(k − 2)\}.

Since |C_{1}| + … + |C_{χ}| = 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χ_{k}(G) ≤ ∑_{i=1}^{χ} ⌈\sqrt{\frac{n}{χ}} ⌉ ≤ χ + \sqrt{χ}\sqrt{n},

and for k ≥ 4, if s denotes the number of vertex classes whose size is less than L(k − 2)^{2} then

Oχ_{k}(G) ≤ sL(k − 2) + (χ − s) ⌈\sqrt{\frac{n}{χ − s}} ⌉ ≤ sL(k − 2) + (χ − s) + \sqrt{χ − s}\sqrt{n}
< χL(k − 2) + χ + \sqrt{χ}\sqrt{n}.

If n is sufficiently large then sL(k − 2) ≤ \sqrt{n}(\sqrt{χ} − \sqrt{χ − s}), and thus

Oχ_{k}(G) ≤ χ + \sqrt{χ}\sqrt{n}.

□

Theorem 1.3 shows that the orthogonal chromatic number of complete partite graphs can be computed exactly. Proof of Theorem 1.3: Let S_{1}, …, 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 ⌈\sqrt{s_{i}} ⌉ ⌊\sqrt{s_{i}}⌋ ≥ s_{i}. We first create an orthogonal coloring \{c_{1}, c_{2}\} with the required number of colors. For i = m+1, …, t we use ⌈\sqrt{s_{i}} ⌉ 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 the electronic journal of combinatorics 6 (1999), #R5 8

set. If m is odd, then S_{m} is also colored with ⌈\sqrt{s_{m}} ⌉ distinct colors in both c_{1} and c_{2}. We now consider the ⌊m/2⌋ pairs of classes {S_{1}, S_{2}}, …, {S_{2⌊m/2⌋−1}, S_{2⌊m/2⌋}}. 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}, …, w_{z}\} be a set of z distinct colors where z = ⌈\sqrt{s_{i}} ⌉ + ⌈\sqrt{s_{i+1}} ⌉ − 1. Consider all the ordered pairs of colors of the form (w_{p}, w_{q}) where 1 ≤ p ≤ ⌊\sqrt{s_{i}}⌋ and 1 ≤ q ≤ ⌈\sqrt{s_{i}} ⌉. 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 ⌊\sqrt{s_{i}}⌋ + 1 ≤ p ≤ z and ⌈\sqrt{s_{i}} ⌉ + 1 ≤ q ≤ 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 ∑_{i=1}^{t} ⌈\sqrt{s_{i}} ⌉ − ⌊m/2⌋ colors. Thus

Oχ(G) ≤ ∑_{i=1}^{t} ⌈\sqrt{s_{i}} ⌉ − ⌊m/2⌋ .

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 ≠ 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} + … + a_{t} colors and c_{2} uses b_{1} + … + b_{t} colors. Since c_{1} and c_{2} are orthogonal, we know that a_{i}b_{i} ≥ s_{i} for i = 1, …, t. The overall number of colors used by the pair {c_{1}, c_{2}} is

max\{∑_{i=1}^{t} a_{i}, ∑_{i=1}^{t} b_{i}\} ≥ ⌈\frac{∑_{i=1}^{t}(a_{i} + b_{i})}{2}⌉ .

Since a_{i}b_{i} ≥ s_{i}, the r.h.s. of the last inequality is minimized when a_{i} +b_{i} = 2 ⌈\sqrt{s_{i}} ⌉ if i > m, and when a_{i} + b_{i} = ⌈\sqrt{s_{i}} ⌉ + ⌊\sqrt{s_{i}}⌋ = 2 ⌈\sqrt{s_{i}} ⌉ − 1 if i ≤ m. Thus,

Oχ(G) ≥ ⌈\frac{∑_{i=1}^{t} 2 ⌈\sqrt{s_{i}} ⌉ − m}{2}⌉ = ∑_{i=1}^{t} ⌈\sqrt{s_{i}} ⌉ − ⌊m/2⌋ .

□ As an example, we have that Oχ(K_{6,6}) = 5 since 6 is not an integer square and 2 · 3 ≥ 6, so m = 2 in this case. Note that the same reasoning yields Oχ(K_{5,5}) = 5 and Oχ(K_{5,4}) = 5. Proof of Theorem 1.4: Consider a d-degenerate ordering {v_{1}, …, v_{n}} of the vertices of G. We need to create a set {c_{1}, …, c_{k}} of k-orthogonal colorings. We prove the theorem by coloring the vertices one by one while maintaining orthogonality. Coloring v_{1}, …, v_{d} is trivial, since we may define, say, c_{j}(v_{i}) = i for all j = 1, …, k and i = 1, …, d. Note that t ≥ d so we are still within bounds. Assume we have successfully colored v_{1}, …, 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 the electronic journal of combinatorics 6 (1999), #R5 9

v_{i} in G which have already been colored. Clearly, |R| ≤ 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 ∉ 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 ∉ R, there are at most \binom{k}{2}(i − d − 1)t^{k−2} illegal extensions. This still leaves at least one legal extension since (t − d)^{k} > \binom{k}{2}(i − d − 1)t^{k−2}. For k = 2 we can solve this inequality explicitly and obtain that if t > d + \sqrt{n − d − 1} then Oχ(G) ≤ t. In particular, Oχ(G) ≤ d + 1 + ⌊\sqrt{n − d − 1}⌋ = d + ⌈\sqrt{n − d} ⌉. □ Theorem 1.4 is rather tight since Oχ(G) ≥ ⌈\sqrt{n} ⌉ always. In fact, for every d, we can show that there exist d-degenerate graphs G for which Oχ(G) = d + ⌈\sqrt{n − d} ⌉. 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 χ(G_{n,d}) = d + 1. We claim that we cannot color G_{n,d} orthogonally with less than d+⌈\sqrt{n − d} ⌉ 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 ⌈\sqrt{n − d} ⌉ colors on I_{n−d}, and, obviously, an additional set of d colors on K_{d}.

3 Optimal and perfect orthogonal colorings

In this section we focus on graphs having a k-OOC or a k-POC. Clearly, if χ(G) > ⌈\sqrt{n} ⌉ then G does not have a k-OOC. Hence, there exist graphs G with Δ(G) = ⌈\sqrt{n} ⌉ which do not have a k-OOC (e.g. any graph G on n vertices with Δ(G) = ⌈\sqrt{n} ⌉ having a clique on ⌈\sqrt{n} ⌉ + 1 vertices as a connected component). It turns out that graphs with a somewhat lower maximum degree, but still with Δ(G) = Ω(\sqrt{n}), always have a k-OOC. This is shown in Theorem 1.5: Proof of Theorem 1.5: Consider the set V of the vertices of G, as a set of n isolated vertices. Since n ≥ L(k − 2)^{2}, we have, by Lemma 2.1, that V has k-OOC. Let c_{1}, …, 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}, …, 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 the electronic journal of combinatorics 6 (1999), #R5 10

subgraph of G, and we assume that c_{1}, …, c_{k} is a k-OOC of G^{∗} \ {e}. If c_{i}(v) ≠ c_{i}(u) for each i = 1, …, k, then c_{1}, …, 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| ≤ Δ = Δ(G). Let W ⊂ V be the set of vertices w having, for some i, and some z ∈ Z, c_{i}(w) = c_{i}(z). (We allow z = w, so Z ∪ {v} ⊂ W). Since the colorings form a k-OOC in G^{∗} \ {e}, we know that each color appears at most ⌈\sqrt{n} ⌉ times in each coloring. Thus, |W | ≤ k|Z| ⌈\sqrt{n} ⌉. Now let Y ⊂ V denote the set of vertices y, other than v, which have c_{i}(y) = c_{i}(v) for some i = 1, …, k. Clearly, |Y | ≤ k(⌈\sqrt{n} ⌉ − 1). Now consider the set Y^{∗} of all the vertices of G^{∗} which have a neighbor in Y. |Y^{∗}| ≤ |Y |Δ. Finally, let X = V \ (W ∪ Y^{∗}). We first show that X is not empty. This is true since

|X| ≥ n − |W | − |Y^{∗}| ≥ n − k|Z| ⌈\sqrt{n} ⌉ − Δ|Y | ≥ n − kΔ ⌈\sqrt{n} ⌉ − kΔ(⌈\sqrt{n} ⌉ − 1) > 0

where the last inequality follows from the fact that Δ ≤ (\sqrt{n}−1)/(2k) < n/(k(2 ⌈\sqrt{n} ⌉−1)). Now let x ∈ 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 ∉ W, and the colorings in the neighborhood of x are proper since x ∉ Y^{∗}, and so it has no neighbor which shares the same color with the original color of v, in any of the k colorings. □

Theorem 1.4 and (1) show that for every n-vertex tree T, ⌈\sqrt{n} ⌉ ≤ Oχ(T) ≤ 1 + ⌈\sqrt{n − 1} ⌉. Thus, Oχ(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 1.4 shows that the star on n vertices, K_{1,n−1}, has Oχ(K_{1,n−1}) = 1+⌈\sqrt{n − 1} ⌉, 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 (⌊\sqrt{n − 1}⌋)^{2} + 1 does not have an OOC. For example, all the trees with 18 ≤ n ≤ 25 vertices which have a vertex of degree 17 do not have an OOC since they contain K_{1,17} and Oχ(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. 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 (⌈\sqrt{n} ⌉)(⌈\sqrt{n} − 1⌉) < 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 the electronic journal of combinatorics 6 (1999), #R5 11

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 ≤ x. Consequently, x(x − 1) ≥ n. Thus, whenever (⌈\sqrt{n} ⌉)(⌈\sqrt{n} − 1⌉) < n, we must have x > ⌈\sqrt{n} ⌉.

4 Strong orthogonal colorings

A k-strong orthogonal coloring, is a k-orthogonal coloring c_{1}, …, c_{k}, where for each vertex v and for every pair of distinct colorings c_{i} and c_{j}, c_{i}(v) ≠ c_{j}(v). The analogous definitions of SOχ_{k}(G) and SOχ(G) are obvious. A graph G is said to have a strong perfect orthogonal coloring (SPOC for short) if it has r(r − 1) vertices and SOχ(G) = r. A graph G with r^{2} vertices is said to have a 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χ(G) ≥ (1 + \sqrt{1 + 4n})/2, and Oχ(G) ≥ \sqrt{n}. It is therefore plausible to conjecture that Oχ(G) ≤ SOχ(G) ≤ Oχ(G) + 1. This, however, is far from being true, as Oχ(U_{4}) = 4 while it is not difficult to check that SOχ(U_{4}) = 6. In fact, it can be shown that SOχ(U_{r}) − Oχ(U_{r}) grows linearly with r. It is possible, however, to prove that SOχ(G) ≤ Oχ(G) + ⌈χ(G)/2⌉. To see this, assume c_{1}, c_{2} is an orthogonal coloring of G with Oχ(G) colors (assume the colors are 1, …, Oχ(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 χ(G) independent sets X_{1}, …, X_{χ(G)}. Now, for every v ∈ X_{i} with i ≤ χ(G)/2 we redefine c_{1}(v) = Oχ(G) + i. For every v ∈ X_{i} with i > χ(G)/2 we redefine c_{2}(v) = Oχ(G) + i − ⌊χ(G)/2⌋. After these modifications, c_{1}, c_{2} is a strong orthogonal coloring of G using at most Oχ(G) + ⌈χ(G)/2⌉ colors. Note that, in particular, every bipartite graph has SOχ(G) ≤ Oχ(G) + 1, and, by Theorem 1.4, every d-degenerate graph has SOχ(G) ≤ ⌈(3d + 1)/2⌉ + ⌈\sqrt{n − d} ⌉.

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 ≠ j and 1 ≤ i ≤ r, 1 ≤ j ≤ r as the vertices, and connect a pair (i, j) to a pair (k, l) with an edge if and only if i ≠ k and j ≠ l. The resulting graph, denoted by W_{r}, has SOχ(W_{r}) = r, and therefore has a SPOC. Also, any graph G having SOχ(G) ≤ r is isomorphic to a subgraph of W_{r}, as can be seen from the obvious isomorphism, where v ∈ 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 ≤ i ≤ r and the electronic journal of combinatorics 6 (1999), #R5 12

1 ≤ j ≤ r + 1, and i ≠ 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 ∈ {2, 3, 6}. In other words, U_{r}^{c} is a spanning subgraph of X_{r}, unless r ∈ {2, 3, 6}. In fact we will show something more general: Consider the grid graph G_{a,b}, where a ≥ b are positive integers. The vertices of G_{a,b} are defined by all pairs of ordered integers (i, j) where 1 ≤ i ≤ a and 1 ≤ j ≤ 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}.

Theorem 4.1

1. Every subgraph G of G_{r,r−1} has SOχ(G) ≤ r. In particular, every spanning subgraph of G_{r,r−1} has a SPOC.

2. For every positive integer r ∉ {2, 3, 6}, every spanning subgraph of G_{r,r} has a strong orthogonal scheme.

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, …, r − 1. Consider first the case where r is odd. We define c_{1}((i, j)) = (i + j − 2) mod r. Next, we define c_{2}((i, j)) = (c_{1}(i, j) + j) mod r. Now, c_{1} is a proper coloring since c_{1}((i, j)) ≠ c_{1}((i, k)) when k ≠ j, and c_{1}((i, j)) ≠ c_{1}((k, j)) when k ≠ 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 ≤ j ≤ 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 ≠ l, and therefore c_{2}((i, j)) ≠ c_{2}((k, l)). Now assume that r is even. We define c_{1}((i, j)) = (i + j − 2) mod r for all 1 ≤ i ≤ r and for all 1 ≤ j ≤ r/2, and we define c_{1}((i, j)) = (i + j − 1) mod r for all 1 ≤ i ≤ r and r/2 + 1 ≤ j ≤ r − 1. We define c_{2}((i, j)) = (c_{1}(i, j) + j) mod 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}. 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 ∉ 2, 3, 6 [5]. 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 ≤ i ≤ r and 1 ≤ j ≤ r. If i ≠ j we define c_{2}((i, j)) = L^{t}(i, j) = L(j, i). Finally, the electronic journal of combinatorics 6 (1999), #R5 13

we define c_{2}((i, i)) = r + 1, for i = 1, …, 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), …, (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), …, (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. □ 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}). □

5 Concluding remarks and open problems

1. Theorem 1.5 shows, in particular, that if Δ(G) ≤ (\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 ≤ 1, as shown in the discussion prior to the proof of Theorem 1.5. The obvious generalization for k > 2 (i.e. replacing the denominator 2k with something smaller) may also be considered.

2. 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χ(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 ⌈\sqrt{n} ⌉ or 1 + ⌈\sqrt{n − 1} ⌉. 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.

3. 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. the electronic journal of combinatorics 6 (1999), #R5 14

4. It would be interesting to determine the exact relationship between Oχ(G) and SOχ(G).

5. A graph G is called [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 [8] which focuses on these graphs). For example, K_{n} is [n, 1, 1]-partite, and C_{9} is [3, 3, 3]-partite. An 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 [8] 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 ([8] Conjecture 1.5). A seemingly easier conjecture is the following: “Does every [k, k, k]-partite graph have a POC?”

References

[1] B. Alspach, K. Heinrich and G. Liu, Orthogonal factorizations of graphs, in: Contemporary Design Theory: A collection of surveys, (J.H. Dinitz and D.R. Stinson eds.), Wiley, 1992, 13-38.

[2] D. Archdeacon, J.H. Dinitz and F. Harary, Orthogonal edge colorings of graphs, Congressus Numerantium 47 (1985), 49-67.

[3] T. Beth, Eine Bemerkung zur Abschätzung der Anzahl orthogonaler lateinischer Quadrate mittels Siebverfahren, Abh. Math. Sem. Univ. Hamburg 53 (1983), 284-288.

[4] B. Bollobás, Extremal Graph Theory, Academic Press, 1978.

[5] R.K. Brayton, D. Coppersmith and A.J. Hoffman, Self-orthogonal Latin squares, Coll. Int. Th. Comb., Rome (1973), Atti del Convegni Lincei No. 17 (1976) 509-517.

[6] C.J. Colbourn and J.H. Dinitz, CRC Handbook of Combinatorial Design, CRC press 1996.

[7] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdös, in: Combinatorial Theory and its Applications, Vol. II (P. Erdös, A. Renyi and V. T. Sós eds.), Colloq. Math. Soc. J. Bolyai 4, North Holland, Amsterdam 1970, 601-623.

[8] R. Yuster, Independent transversals and independent coverings in sparse partite graphs, Combinatorics, Probability and Computing 6 (1997), 115-125.