Avoiding rainbow induced subgraphs in edge-colorings

被引:0
作者
Sackett, Chelsea [1 ]
Axenovich, Maria [1 ]
机构
[1] Iowa State Univ, Dept Math, Ames, IA 50011 USA
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2009年 / 44卷
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let H be a fixed graph on k edges. For an edge-coloring c of H, we say that H is rainbow, or totally multicolored if c assigns distinct colors to all edges of H. We show, that it is easy to avoid rainbow induced graphs H. Specifically, we prove that for any graph H (with some notable exceptions), and for any graph G, G not equal H, there is an edge -coloring of G with k colors which contains no induced rainbow subgraph isomorphic to H. This demonstrates that, in a sense, induced subgraphs do not have "anti-Ramsey" -type properties.
引用
收藏
页码:287 / 296
页数:10
相关论文
共 50 条
[21]   Some rainbow cycles in r-good edge-colorings [J].
Liu, Zi-Long ;
Tian, Fang .
APPLIED MATHEMATICS AND COMPUTATION, 2019, 362
[22]   EDGE-COLORINGS OF GRAPHS [J].
ANDERSEN, LD .
MATHEMATICA SCANDINAVICA, 1977, 40 (02) :161-175
[23]   Large rainbow matchings in semi-strong edge-colorings of graphs [J].
Jin, Zemin ;
Ye, Kun ;
Chen, He ;
Sun, Yuefang .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (02)
[24]   Edge-colorings of complete bipartite graphs without large rainbow trees [J].
Jin, Zemin ;
Li, Lifen .
ARS COMBINATORIA, 2013, 111 :75-84
[25]   MAXIMAL EDGE-COLORINGS OF GRAPHS [J].
Babinski, S. ;
Grzesik, A. .
ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03) :403-407
[26]   MAXIMUM EDGE-COLORINGS OF GRAPHS [J].
Jendrol, Stanislav ;
Vrbjarova, Michaela .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) :117-125
[27]   On restricted edge-colorings of bicliques [J].
Mubayi, D ;
West, DB .
DISCRETE MATHEMATICS, 2002, 257 (2-3) :513-529
[28]   Majority Edge-Colorings of Graphs [J].
Bock, Felix ;
Kalinowski, Rafal ;
Pardey, Johannes ;
Pilsniak, Monika ;
Rautenbach, Dieter ;
Wozniak, Mariusz .
ELECTRONIC JOURNAL OF COMBINATORICS, 2023, 30 (01) :1-8
[29]   UNIQUENESS OF IMPARTIAL EDGE-COLORINGS [J].
ELLINGHAM, MN ;
CARO, Y .
ARS COMBINATORIA, 1986, 22 :59-71
[30]   Maximal Edge-Colorings of Graphs [J].
Meszka, Mariusz ;
Tyniec, Magdalena .
GRAPHS AND COMBINATORICS, 2017, 33 (06) :1451-1458