2021/05/12 by Johannes Pardey, Dieter Rautenbach, Pardey, Johannes +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2105.05661
openalex publication_date 2021/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G and a not necessarily proper k-edge coloring c:E(G)\→ \n1,\…,k , let mi(G) be the number of edges of G of color i, and\ncall G it color-balanced if mi(G)=mj(G) for every two colors i and\nj. Several famous open problems relate to this notion; Ryser's conjecture on\ntransversals in latin squares, for instance, is equivalent to the statement\nthat every properly n-edge colored complete bipartite graph Kn,n has a\ncolor-balanced perfect matching. We contribute some results on the question\nposed by Kittipassorn and Sinsap (arXiv:2011.00862v1) whether every k-edge\ncolored color-balanced complete graph K2kn has a color-balanced perfect\nmatching M. For a perfect matching M of K2kn, a natural measure for\nthe total deviation of M from being color-balanced is\nf(M)=\∑\i=1k|mi(M)-n|. While not every color-balanced complete\ngraph K2kn has a color-balanced perfect matching M, that is, a perfect\nmatching with f(M)=0, we prove the existence of a perfect matching M with\nf(M)=O\(k\√(kn\ln(k))\) for general k and f(M)\≤ 2 for\nk=3; the case k=2 has already been studied earlier. An attractive feature\nof the problem is that it naturally invites the combination of a combinatorial\napproach based on counting and local exchange arguments with probabilistic and\ngeometric arguments.\n