Abstract
A pair of orthogonal one-factorizations \(\mathcal F\) and \({\mathcal {G}}\) of the complete graph \(K_n\) is \(C_4\)-free if for any two factors \(F\in {\mathcal {F}}\) and \(G\in {\mathcal {G}}\) the union \(F\cup G\) does not include a cycle of length four. Such a concept was introduced by Blokhuis et al. (J Combin Theory B 82: 1–18, 2001), who used it to improve the upper bound for two-round rainbow colorings of \(K_n\). In this paper, we focus on constructions for a pair of orthogonal \(C_4\)-free one-factorizations of the complete graph \(K_n\). Some infinite classes of such orthogonal decompositions are obtained.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alspach, B., Heinrich, K., Liu, G.: Orthogonal factorizations of graphs. In: Dinitz, J.H., Stinson, D.R. (eds.) Contemporary Design Theory, pp. 13–40. Wiley, New York (1992)
Blokhuis, A., Faudree, R., Gyárfás, A., Ruszinkó, M.: Anti-ramsey colorings in several rounds. J. Combin. Theory B 82, 1–18 (2001)
Heinrich, K.: Latin squares with and without subsquares of prescribed type. In: Denes, J., Keedwell, A.D. (eds.) Latin Squares: New Developments in the Theory and Applications, Ann. Discrete Math. 46, pp. 101–147. North-Holland, Amsterdam (1991)
Dickson, L.E.: Cyclotomy, higher congruences and Waring’s problem. Am. J. Math 57, 391–424 (1935)
Dinitz, J.H., Dukes, P.: On the structure of uniform one-factorizations from starters in finite fields. Finite Fields Appl. 12, 283–300 (2006)
Dinitz, J. H., Dukes, P., Stinson, D.R.: Sequentially perfect and uniform one-factorizations of the complete graph. Electron. J. Combin., 12, \(\sharp \) R1 (2005)
Horton, J.D.: Room designs and one-factorizations. Aequ. Math. 22, 56–63 (1981)
Horton, J.D.: Quintuplication of Room squares. Aequ. Math. 7, 243–245 (1971)
Mendelsohn, E., Rosa, A.: One-factorizations of the complete graph-a survey. J. Graph. Theory 9, 43–65 (1985)
Meszka, M.: \(k\)-cycle free one-factorizations of complete graphs. Electron. J. Combin., 16, \(\sharp \)R3 (2009)
Mullin, R.C., Nemeth, E.: A counterexample to a multiplicative construction of Room squares. J. Combin. Theory 7, 266–272 (1969)
Phelps, K., Stinson, D.R., Vanstone, S.A.: The existence of simple \(S_3(3,4, v)\). Discrete Math. 77, 255–258 (1989)
Stanton, R.G., Horton, J.D.: A multiplication theorem for Room squares. J. Combin. Theory 12, 322–325 (1972)
Stanton, R.G., Mullin, R.C.: Construction of Room squares. Ann. Math. Stat. 39, 1540–1548 (1968)
Storer, T.: Cyclotomy and Difference Sets. Markham, Chicago (1967)
Wallis, W.D.: One-factorizations of complete graphs. In: Dinitz, J.H., Stinson, D.R. (eds.) Contemporary Design Theory, pp. 593–631. Wiley, New York (1992)
Wallis, W.D.: A Room square of size \(257\). Congr. Numer. 8, 533 (1973)
Acknowledgements
The authors would like to thank the referees for carefully checking and many helpful comments on the paper. Part of the research of J. Bao was supported by NSFC grant 11701303 and the K. C. Wong Magna Fund in Ningbo University. Part of the research of L. Ji was supported by NSFC Grants 11871363, 11431003.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bao, J., Ji, L. Two Orthogonal 4-Cycle-Free One-Factorizations of Complete Graphs. Graphs and Combinatorics 35, 373–392 (2019). https://doi.org/10.1007/s00373-018-2000-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-018-2000-y