The rainbow Turan number of P5

被引:0
作者
Halfpap, Anastasia [1 ]
机构
[1] Iowa State Univ, Dept Math, Ames, IA 50011 USA
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2023年 / 87卷
关键词
PATHS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An edge-colored graph F is rainbow if each edge of F has a unique color. The rainbow Turan number ex & lowast;(n, F) of a graph F is the maximum possible number of edges in a properly edge-colored n-vertex graph with no rainbow copy of F. The study of rainbow Turan numbers was introduced by Keevash, Mubayi, Sudakov, and Verstrete in 2007. In this paper we focus on ex & lowast;(n, P5). While several recent papers have investigated rainbow Tur<acute accent>an numbers for -edge paths P-e, exact results have only been obtained for < 5, and P-5 represents one of the smallest cases left open in rainbow Tur<acute accent>an theory. In this paper, we prove that ex & lowast;(n, P5) <= 5n 2 . Combined with a lower-bound construction due to Johnston and Rombach, this result shows that ex & lowast;(n, P5) = 5n /2 when n is divisible by 16, thereby settling the question asymptotically for all n. In addition, this result strengthens the conjecture that ex & lowast;(n, P) = e/2n+O(1) for all >= 3
引用
收藏
页码:403 / 422
页数:20
相关论文
共 10 条
  • [1] Many T copies in H-free graphs
    Alon, Noga
    Shikhelman, Clara
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 : 146 - 172
  • [2] Rainbow Turan problem for even cycles
    Das, Shagnik
    Lee, Choongbum
    Sudakov, Benny
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (05) : 905 - 915
  • [3] Ergemlidze B, 2019, ELECTRON J COMB, V26
  • [4] Generalized rainbow Turan problems
    Gerbner, Daniel
    Methuku, Abhishek
    Meszaros, Tamas
    Palmer, Cory
    [J]. ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (02)
  • [5] Halfpap A, 2021, AUSTRALAS J COMB, V81, P152
  • [6] Janzer O., 2020, arXiv
  • [7] Johnston D, 2020, AUSTRALAS J COMB, V78, P61
  • [8] Johnston D, 2017, ELECTRON J COMB, V24
  • [9] Rainbow Turan problems
    Keevash, Peter
    Mubayi, Dhruv
    Sudakov, Benny
    Verstraete, Jacques
    [J]. COMBINATORICS PROBABILITY & COMPUTING, 2007, 16 (01) : 109 - 126
  • [10] ON A PROBLEM OF HAHN,G. ABOUT COLORED HAMILTONIAN PATHS IN K2N
    MAAMOUN, M
    MEYNIEL, H
    [J]. DISCRETE MATHEMATICS, 1984, 51 (02) : 213 - 214