Disjoint properly colored cycles in edge-colored complete bipartite graphs

被引：1

作者：

Yoshimoto, Kiyoshi ^{[1
]}

机构：

[1] Nihon Univ, Coll Sci & Technol, Dept Math, Tokyo 1018308, Japan

来源：

DISCRETE MATHEMATICS | 2023年 / 346卷 / 01期

关键词：

Edge-colored graphs; Complete bipartite graphs; Digraphs; Bermond and Thomassen?s conjecture; Disjoint cycles; Properly colored cycles; BERMOND-THOMASSEN CONJECTURE; ALTERNATING CYCLES;

D O I：

10.1016/j.disc.2022.113095

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let K-n,K-m be an edge-colored complete bipartite graph with 1 < n < m and delta(mon)(K-n,K-m) be the number of the leaves of a maximum monochromatic star in K-n,K-m. In this paper, we show that if delta(mon)(K-n,K-m) < n - 2k +1, then K-n,K-m has k disjoint properly colored cycles. (C) 2022 Elsevier B.V. All rights reserved.

引用

页数：6

共 14 条

[1] Local anti-Ramsey numbers of graphs [J].

Axenovich, M ;

Jiang, T ;

Tuza, Z .

COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (5-6) :495-511

[2] Vertex-disjoint cycles in bipartite tournaments [J].

Bai, Yandong ;

Li, Binlong ;

Li, Hao .

DISCRETE MATHEMATICS, 2015, 338 (08) :1307-1309

[3]

Bang-Jensen J., 2001, DIGRAPHS THEORY ALGO

[4] Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments [J].

Bang-Jensen, Jorgen ;

Bessy, Stephane ;

Thomasse, Stephan .

JOURNAL OF GRAPH THEORY, 2014, 75 (03) :284-302

[5] CYCLES IN DIGRAPHS - A SURVEY [J].

BERMOND, JC ;

THOMASSEN, C .

JOURNAL OF GRAPH THEORY, 1981, 5 (01) :1-43

[6] A complete bipartite graph without properly colored cycles of length four [J].

Cada, Roman ;

Ozeki, Kenta ;

Yoshimoto, Kiyoshi .

JOURNAL OF GRAPH THEORY, 2020, 93 (02) :168-180

[7]

Erdo P., 1993, QUO VADIS GRAPH THEO, V55, P81

[8] Color degree and monochromatic degree conditions for short properly colored cycles in edge-colored graphs [J].

Fujita, Shinya ;

Li, Ruonan ;

Zhang, Shenggui .

JOURNAL OF GRAPH THEORY, 2018, 87 (03) :362-373

[9] ALTERNATING CYCLES IN EDGE-PARTITIONED GRAPHS [J].

GROSSMAN, JW ;

HAGGKVIST, R .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (01) :77-81

[10] Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs [J].

Li, Ruonan ;

Broersma, Hajo ;

Zhang, Shenggui .

JOURNAL OF GRAPH THEORY, 2020, 94 (03) :476-493

← 1 2 →