A Rainbow k-Matching in the Complete Graph with r Colors

被引：0

作者：

Fujita, Shinya ^{[1
]}

Kaneko, Atsushi

Schiermeyer, Ingo ^{[2
]}

Suzuki, Kazuhiro ^{[3
]}

机构：

[1] Gunma Natl Coll Technol, Dept Math, Gunma 3718530, Japan

[2] Tech Univ Bergakad Freiberg, Inst Diskrete Math & Algebra, D-09596 Freiberg, Germany

[3] Ibaraki Univ, Dept Comp & Informat Sci, Ibaraki 3168511, Japan

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2009年 / 16卷 / 01期

关键词：

edge-coloring; matching; complete graph; anti-Ramsey; rainbow; heterochromatic; totally multicolored;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An r-edge-coloring of a graph is an assignment of r colors to the edges of the graph. An exactly r-edge-coloring of a graph is an r-edge-coloring of the graph that uses all r colors. A matching of an edge-colored graph is called rainbow matching, if no two edges have the same color in the matching. In this paper, we prove that an exactly r-edge-colored complete graph of order n has a rainbow matching of size k(>= 2) if r >= max{(2k-3 2) + 2, (k-2 2) + (k-2)(n-k + 2) +2}, k >= 2, and n >= 2k + 1. The bound on r is best possible.

引用

页数：13

共 6 条

[1]

Erdos P., 1975, Colloq. Math. Soc. Janos Bolya, V10, P633

[2]

Erdos Paul, 1959, Acta Math. Acad. Sci. Hungar, V10, P337, DOI [10.1007/bf02024498, DOI 10.1007/BF02024498]

[3]

Eroh L., 2004, Journal of Combinatorial Mathematics and Combinatorial Computing, V51, P175

[4]

Eroh L., 2004, B I COMBIN APPL, V40, P91

[5] An anti-Ramsey theorem [J].

Montellano-Ballesteros, JJ ;

Neumann-Lara, V .

COMBINATORICA, 2002, 22 (03) :445-449

[6] Rainbow numbers for matchings and complete graphs [J].

Schiermeyer, I .

DISCRETE MATHEMATICS, 2004, 286 (1-2) :157-162

← 1 →