Note on rainbow cycles in edge-colored graphs

被引:2
作者
Chen, Xiaozheng [1 ,2 ]
Li, Xueliang [1 ,2 ]
机构
[1] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[2] Nankai Univ, LPMC, Tianjin 300071, Peoples R China
关键词
Edge-coloring; Edge-colored graph; Rainbow cycle; Color-degree condition;
D O I
10.1016/j.disc.2022.113082
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let Gbe a graph of order nwith an edge-coloring c, and let delta(c)(G) denote the minimum color-degree of G. A subgraph Fof Gis called rainbow if all edges of Fhave pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if delta(c)(G) > 2n-1/3, then every vertex of Gis contained in a rainbow triangle; (ii) if delta(c)(G) > 2n-1/3and n >= 13, then every vertex of Gis contained in a rainbow C-4; (iii) if G is complete, n >= 7k - 17and delta(c)(G) > n-1/2+ k, then Gcontains a rainbow cycle of length at least k, where k >= 5.
引用
收藏
页数:12
相关论文
共 9 条
  • [1] Bondy J A, 2008, GRADUATE TEXTS MATH, V244
  • [2] Rainbow cycles in edge-colored graphs
    Cada, Roman
    Kaneko, Atsushi
    Ryjacek, Zdenek
    Yoshimoto, Kiyoshi
    [J]. DISCRETE MATHEMATICS, 2016, 339 (04) : 1387 - 1392
  • [3] Color Degree Condition for Long Rainbow Paths in Edge-Colored Graphs
    Chen, He
    Li, Xueliang
    [J]. BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2016, 39 (01) : 409 - 425
  • [4] On odd rainbow cycles in edge-colored graphs
    Czygrinow, Andrzej
    Molla, Theodore
    Nagle, Brendan
    Oursler, Roy
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2021, 94
  • [5] Properly colored paths and cycles
    Fujita, Shinya
    Magnant, Colton
    [J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (14) : 1391 - 1397
  • [6] Rainbow triangles in edge-colored graphs
    Li, Binlong
    Ning, Bo
    Xu, Chuandong
    Zhang, Shenggui
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2014, 36 : 453 - 459
  • [7] Rainbow C3's and C4's in edge-colored graphs
    Li, Hao
    [J]. DISCRETE MATHEMATICS, 2013, 313 (19) : 1893 - 1896
  • [8] Color degree and heterochromatic cycles in edge-colored graphs
    Li, Hao
    Wang, Guanghui
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2012, 33 (08) : 1958 - 1964
  • [9] Tangjai W, 2017, Arxiv, DOI arXiv:1708.04187