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 条
[41]   DENSITIES, MATCHINGS, AND FRACTIONAL EDGE-COLORINGS [J].
Chen, Xujin ;
Zang, Wenan ;
Zhao, Qiulan .
SIAM JOURNAL ON OPTIMIZATION, 2019, 29 (01) :240-261
[42]   Interval edge-colorings of complete graphs [J].
Khachatrian, H. H. ;
Petrosyan, P. A. .
DISCRETE MATHEMATICS, 2016, 339 (09) :2249-2262
[43]   ON A CLASS OF COMPLETABLE PARTIAL EDGE-COLORINGS [J].
ROSA, A .
DISCRETE APPLIED MATHEMATICS, 1992, 35 (03) :293-299
[44]   On vertex-parity edge-colorings [J].
Borut Lužar ;
Mirko Petruševski ;
Riste Škrekovski .
Journal of Combinatorial Optimization, 2018, 35 :373-388
[45]   MINIMAL EDGE-COLORINGS OF COMPLETE GRAPHS [J].
CAMERON, PJ .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1975, 11 (OCT) :337-346
[46]   Reconfiguration of list edge-colorings in a graph [J].
Ito, Takehiro ;
Kaminski, Marcin ;
Demaine, Erik D. .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (15) :2199-2207
[47]   Equitable Edge-Colorings of Simple Graphs [J].
Zhang, Xia ;
Liu, Guizhen .
JOURNAL OF GRAPH THEORY, 2011, 66 (03) :175-197
[48]   On Interval Edge-Colorings of Bipartite Graphs [J].
Petrosyan, Petros ;
Khachatrian, Hrant ;
Mamikonyan, Tigran .
TENTH INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND INFORMATION TECHNOLOGIES REVISED SELECTED PAPERS CSIT-2015, 2015, :71-76
[49]   Generalized edge-colorings of weighted graphs [J].
Obata, Yuji ;
Nishizeki, Takao .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2016, 8 (01)
[50]   VERTEX COLORINGS WITHOUT RAINBOW SUBGRAPHS [J].
Goddard, Wayne ;
Xu, Honghai .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (04) :989-1005