Physical Sciences and Mathematics Commons^™

Rainbow Perfect And Near-Perfect Matchings In Complete Graphs With Edges Colored By Circular Distance, Shuhei Saitoh, Naoki Matsumoto, Wei Wu

Theory and Applications of Graphs

Given an edge-colored complete graph K_n on n vertices, a perfect (respectively, near-perfect) matching M in K_n with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of K_n by circular distance, and we denote the resulting complete graph by K^●_n. We show that when K^●_n has an even number of vertices, it contains a rainbow perfect matching if and only if n=8k or n=8k+2, where k is a nonnegative integer. In the case of an odd …