Short rainbow cycles for families of matchings and triangles

被引:0
作者
Guo, He [1 ]
机构
[1] Umea Univ, Dept Math & Math Stat, S-90187 Umea, Sweden
关键词
generalized Caccetta-Haggkvist conjecture; rainbow girth; short rainbow cycles; GIRTH;
D O I
10.1002/jgt.23183
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A generalization of the famous Caccetta-Haggkvist conjecture, suggested by Aharoni, is that any family F = (F-1,..., F-n) of sets of edges in K-n, each of size k, has a rainbow cycle of length at most inverted right perpendicularn/kinverted left perpendicular. In works by the author with Aharoni and by the author with Aharoni, Berger, Chudnovsky, and Zerbib, it was shown that asymptotically this can be improved to O(log n) if all sets are matchings of size 2, or all are triangles. We show that the same is true in the mixed case, that is, if each F-i is either a matching of size 2 or a triangle. We also study the case that each F-i is a matching of size 2 or a single edge, or each F-i is a triangle or a single edge, and in each of these cases we determine the threshold proportion between the types, beyond which the rainbow girth goes from linear to logarithmic.
引用
收藏
页码:325 / 336
页数:12
相关论文
共 39 条
  • [1] RAINBOW CYCLES FOR FAMILIES OF MATCHINGS
    Aharoni, Ron
    Guo, He
    ISRAEL JOURNAL OF MATHEMATICS, 2023, 256 (01) : 1 - 8
  • [2] Short rainbow cycles in graphs and matroids
    DeVos, Matt
    Drescher, Matthew
    Funk, Daryl
    Gonzalez Hermosillo de la Maza, Sebastian
    Guo, Krystal
    Huynh, Tony
    Mohar, Bojan
    Montejano, Amanda
    JOURNAL OF GRAPH THEORY, 2021, 96 (02) : 192 - 202
  • [3] Uniquely restricted matchings in subcubic graphs without short cycles
    Fuerst, M.
    Rautenbach, D.
    JOURNAL OF GRAPH THEORY, 2021, 96 (04) : 578 - 593
  • [4] New families of graphs without short cycles and large size
    Abajo, E.
    Balbuena, C.
    Dianez, A.
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (11) : 1127 - 1135
  • [5] Minimum Weight Cycles and Triangles: Equivalences and Algorithms
    Roditty, Liam
    Williams, Virginia Vassilevska
    2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 180 - 189
  • [6] LARGE SUBGRAPHS WITHOUT SHORT CYCLES
    Foucaud, F.
    Krivelevich, M.
    Perarnau, G.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) : 65 - 78
  • [7] A SHORT CONSTRUCTION OF HIGHLY CHROMATIC DIGRAPHS WITHOUT SHORT CYCLES
    Severino, Michael
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2014, 9 (02) : 91 - 94
  • [8] 2-Distance coloring of planar graphs without triangles and intersecting 4-cycles
    Bu, Yuehua
    Zhang, Zewei
    Zhu, Hongguo
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (02)
  • [9] Signless Laplacian spectral radius of graphs without short cycles or long cycles
    Chen, Wenwen
    Wang, Bing
    Zhai, Mingqing
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 645 : 123 - 136
  • [10] TOUGH RAMSEY GRAPHS WITHOUT SHORT CYCLES
    ALON, N
    JOURNAL OF ALGEBRAIC COMBINATORICS, 1995, 4 (03) : 189 - 195