Perfect proper edge colorings of regular bipartite graphs with rainbow C4-s

We call a proper edge coloring of a bipartite graph G = [ X , Y ] with | X | = | Y | = n a B-coloring if every 4-cycle of G is colored with four different colors. Denote by q B ( G ) the smallest number of colors needed for a B-coloring of graph G . The question whether q B ( G ) = n implies | E ( G ) | = o ( n 2 ) is from Burr, Erdős, Graham and Sós. A positive answer to this question would imply a positive answer to the famous ( 7 , 4 ) -conjecture of Brown, Erdős and Sós. Here we look at an interesting test case of this question. We call a B-coloring of a d -regular bipartite graph G = [ X , Y ] with | X | = | Y | = n perfect if each color class forms a perfect matching in G (i.e. has n edges). Let f ( d ) be the minimal n such that there exists a perfect B-coloring of some d -regular bipartite graph G = [ X , Y ] with | X | = | Y | = n . A test case of the question above is whether f ( d ) is super-linear. We prove the affirmative answer for shifted colorings : defined by the matchings M i M i = { ( x k , y k + i ) | 0 ≤ k ≤ n − 1 , i ∈ D } , where D = { i 1 , … , i d } ⊂ [ 0 , n − 1 ] and k + i is computed mod n . Using the Induced matching lemma of Szemerédi, we extend this result to a more general class of colorings that we call translation invariant colorings. In general, we show 2 d + 1 ≤ f ( d ) for odd d , 2 d − 1 ≤ f ( d ) for even d and equality may hold only for incidence graphs of certain symmetric designs. From Behrend's construction we get f ( d ) ≤ d e c log ⁡ d . To find exact values of f ( d ) is not easy even for small values of d . We show that f ( 3 ) = 7 , f ( 4 ) = 8 , f ( 5 ) = 12 , 12 ≤ f ( 6 ) ≤ 14 , f ( 7 ) = 16 , using properties of small biplanes and symmetric designs.