Minimum-degree conditions for rainbow triangles

被引:2
作者
Falgas-Ravry, Victor [1 ]
Markstrom, Klas [1 ]
Raty, Eero [1 ]
机构
[1] Umea Univ, Inst Matemat & Matemat Stat, Umea, Sweden
基金
瑞典研究理事会;
关键词
extremal graph theory; Gallai colourings; Mantel's theorem; min degree; rainbow triangles; LINEAR-TIME ALGORITHM; EMBEDDING GRAPHS; COMPLEXITY; TREEWIDTH; VERTICES; MINORS;
D O I
10.1002/jgt.23109
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G:=(G(1),G(2),G(3)) be a triple of graphs on a common vertex set V of size n. A rainbow triangle in G is a triple of edges (e(1),e(2),e(3)) with ei is an element of Gi for each i and {e(1),e(2),e(3)} forming a triangle in V. In this paper we consider the following question: what triples of minimum degree conditions (delta(G(1)),delta(G(2)),delta(G(3))) guarantee the existence of a rainbow triangle? This may be seen as a minimum degree version of a problem of Aharoni, DeVos, de la Maza, Montejanos and & Scaron;& aacute;mal on density conditions for rainbow triangles, which was recently resolved by the authors. We establish that the extremal behaviour in the minimum degree setting differs strikingly from that seen in the density setting, with discrete jumps as opposed to continuous transitions. Our work leaves a number of natural questions open, which we discuss.
引用
收藏
页码:298 / 329
页数:32
相关论文
共 19 条
[1]  
Aharoni R., 2020, Adv. Comb, P1
[2]   Rainbow triangles and the Caccetta-Haggkvist conjecture [J].
Aharoni, Ron ;
DeVos, Matthew ;
Holzman, Ron .
JOURNAL OF GRAPH THEORY, 2019, 92 (04) :347-360
[3]  
Andrasfai B., 1974, Discrete Mathematics, V8, P205, DOI 10.1016/0012-365X(74)90133-2
[4]  
Cameron K, 1997, J GRAPH THEOR, V26, P9, DOI 10.1002/(SICI)1097-0118(199709)26:1<9::AID-JGT2>3.0.CO
[5]  
2-N
[6]  
Clinch K., 2022, arXiv preprint arXiv:2211.07897
[7]  
Diwan A., 2006, PREPRINT
[8]  
Erdos P., 1993, Quo Vadis, Graph Theory, P81
[9]  
FalgasRavry V., Combinatorica
[10]   TRANSITIV ORIENTIERBARE GRAPHEN [J].
GALLAI, T .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2) :25-&