Rainbow saturation of graphs
Rainbow saturation of graphs
复制标题
DOI：
10.1002/jgt.22532
复制
发表时间：
2017-10
影响因子：
0.9
通讯作者：
António Girão;David Lewis;Kamil Popielarz
中科院分区：
文献类型：
--
作者：
António Girão;David Lewis;Kamil Popielarz
在本文中，我们研究了 Barrus、Ferrara、Vandenbussche 和 Wenger 提出的以下问题。给定一个图 H 和一个整数 t ， satt(n,R(H)) 是多少，t 边彩色图 G 在 n 个顶点上的最小边数，使得 G 不包含 H 的彩虹副本，但向 G 添加来自 {1,2,…,t} 的任何颜色的新边会创建 H 的彩虹副本？在这里，对于属于一大类连通图的任何图 H 以及任何 t≥e(H) ，我们将 satt(n,R(H)) 的增长率完全描述为 n 的函数。该分类包括所有最小度为 2 的连通图。特别地，我们证明了 satt(n,R(Kr))=θ(nlogn) ，对于任何 r≥3 和 t≥r2 ，从而解决了 Barrus、Ferrara、Vandenbussche 和 Wenger 的猜想。我们还提出了一些新问题和猜想。
In this paper, we study the following problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger. Given a graph H and an integer t , what is satt(n,R(H)) , the minimum number of edges in a t ‐edge‐colored graph G on n vertices such that G does not contain a rainbow copy of H , but adding to G a new edge in any color from {1,2,…,t} creates a rainbow copy of H ? Here, we completely characterize the growth rates of satt(n,R(H)) as a function of n , for any graph H belonging to a large class of connected graphs and for any t≥e(H) . This classification includes all connected graphs of minimum degree 2. In particular, we prove that satt(n,R(Kr))=Θ(nlogn) , for any r≥3 and t≥r2 , thus resolving a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We also pose several new problems and conjectures.