An application of splittable 4-frames to coloring of \(K_{n,n}\) (Q1861305)

The paper contains two types of results. In the first part, the author considers the existence of an incidence structure called a splittable \(4\)-frame of type \(6^u\) which is a special group divisible design whose block set admits a partition into holey parallel classes and a certain additional structure. In the main result of this section it is shown that a splittable \(4\)-frame of type \(6^u\) exists for every \( u \equiv 1 \pmod{4} \). The proof is based on a clever use of several related structures together with some more general constructions. In the second part, the design found in the first part is used to color the edges of \(K_{n,n}\) in order to obtain a weak \((C_4,3) \)-coloring -- a coloring of the edges of \(K_{n,n}\) in which every copy of \(C_4\) has at least three colors or is alternately \(2\)-colored. This coloring allows the author to obtain the upper bound \( r'(K_{n,n},C_4,3) \leq \lfloor 2n/3 \rfloor +9\) for the minimum number of colors in a weak \((C_4,3)\)-coloring of \(K_{n,n}\). This is a result that improves results previously obtained by \textit{M. Axenovich} et al. [J. Comb. Theory, Ser. B 79, 66-86 (2000; Zbl 1023.05101)]. It is also the best possible result since \(r'(K_{n,n},C_4,3) > \lfloor 2n/3 \rfloor \) was already shown by Axenovich et al.