Directed Graphs Without Rainbow Triangles

被引:0
作者
Babinski, Sebastian [1 ]
Grzesik, Andrzej [1 ]
Prorok, Magdalena [2 ]
机构
[1] Jagiellonian Univ, Fac Math & Comp Sci, Krakow, Poland
[2] AGH Univ Sci & Technol, Krakow, Poland
关键词
directed graphs; rainbow triangle; Tur & aacute; n problem;
D O I
10.1002/jgt.23224
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
One of the most fundamental results in graph theory is Mantel's theorem which determines the maximum number of edges in a triangle-free graph of order n $n$. Recently, a colorful variant of this problem has been solved. In this variant we consider c $c$ graphs on a common vertex set, think of each graph as edges in a distinct color, and want to determine the smallest number of edges in each color which guarantees the existence of a rainbow triangle. Here, we solve the analogous problem for directed graphs without rainbow triangles, either directed or transitive, for any number of colors. The constructions and proofs essentially differ for c = 3 $c=3$ and c >= 4 $c\ge 4$ and the type of the forbidden triangle. Additionally, we also solve the analogous problem in the setting of oriented graphs.
引用
收藏
页码:269 / 281
页数:13
相关论文
共 13 条
[1]  
Aharoni R., 2020, Advances in Combinatorics, P12043
[2]   GRAPHS WITHOUT A RAINBOW PATH OF LENGTH 3 [J].
Babinski, Sebastian ;
Grzesik, Andrzej .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (01) :629-644
[3]   On a rainbow extremal problem for color-critical graphs [J].
Chakraborti, Debsoumya ;
Kim, Jaehoon ;
Lee, Hyunwoo ;
Liu, Hong ;
Seo, Jaehyeon .
RANDOM STRUCTURES & ALGORITHMS, 2024, 64 (02) :460-489
[4]  
Diwan A., 2007, MUBAYI TURANS THEORE
[5]   Minimum-degree conditions for rainbow triangles [J].
Falgas-Ravry, Victor ;
Markstrom, Klas ;
Raty, Eero .
JOURNAL OF GRAPH THEORY, 2024, 107 (02) :298-329
[6]   Rainbow Variations on a Theme by Mantel: Extremal Problems for Gallai Colouring Templates [J].
Falgas-Ravry, Victor ;
Markstrom, Klas ;
Raty, Eero .
COMBINATORICA, 2024, 44 (05) :977-1010
[7]  
Frankl P., 2022, ARXIV
[8]   Directed graphs without rainbow stars [J].
Gerbner, Daniel ;
Grzesik, Andrzej ;
Palmer, Cory ;
Prorok, Magdalena .
ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (04)
[9]   A general approach to transversal versions of Dirac-type theorems [J].
Gupta, Pranshu ;
Hamann, Fabian ;
Muyesser, Alp ;
Parczyk, Olaf ;
Sgueglia, Amedeo .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2023, 55 (06) :2817-2839
[10]   Extremal Results for Graphs Avoiding a Rainbow Subgraph [J].
He, Zhen ;
Frankl, Peter ;
Gyori, Ervin ;
Lv, Zequn ;
Salia, Nika ;
Tompkins, Casey ;
Varga, Kitti ;
Zhu, Xiutao .
ELECTRONIC JOURNAL OF COMBINATORICS, 2024, 31 (01)