GRAPHS WITHOUT A RAINBOW PATH OF LENGTH 3

被引：3

作者：

Babinski, Sebastian ^{[1
]}

Grzesik, Andrzej ^{[1
]}

机构：

[1] Jagiellonian Univ, Fac Math & Comp Sci, P-30 348 Krakow, Poland

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2024年 / 38卷 / 01期

关键词：

extremal graph theory; rainbow coloring; Turan-type problems; TURAN PROBLEM; NUMBERS;

D O I：

10.1137/22M1535048

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In 1959, ErdoH \s and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. Here, we study a rainbow version of their theorem, in which one considers k \geq 1 graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any k \geq 1.

引用

页码：629 / 644

页数：16

共 25 条

[1]

AHARONI R., 2020, Adv. Comb, P12, DOI DOI 10.19086/AIC.12043

[2]

[Anonymous], 1907, Wiskundige Opgaven

[3] Generalized rainbow Turan numbers of odd cycles [J].

Balogh, Jozsef ;

Delcourt, Michelle ;

Heath, Emily ;

Li, Lina .

DISCRETE MATHEMATICS, 2022, 345 (02)

[4]

CULVER E., A Colorful Version of Mantel's Theorem

[5] Rainbow Turan problem for even cycles [J].

Das, Shagnik ;

Lee, Choongbum ;

Sudakov, Benny .

EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (05) :905-915

[6]

DeVos M, 2019, ELECTRON J COMB, V26

[7]

DIWAN A., 2007, Tura'\n's Theorem with Colors

[8] ON THE STRUCTURE OF LINEAR GRAPHS [J].

ERDOS, P ;

STONE, AH .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091

[9]

Erdos P., 1959, ACTA MATH ACAD SCI H, V10, P337, DOI DOI 10.1007/BF02024498

[10]

Ergemlidze B, 2019, ELECTRON J COMB, V26

← 1 2 3 →