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 条
[31]   Nonrepetitive edge-colorings of trees [J].
Kuendgen, Andre ;
Talbot, Tonya .
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2017, 19 (01)
[32]   ANTIPODAL EDGE-COLORINGS OF HYPERCUBES [J].
West, Douglas B. ;
Wise, Jennifer, I .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) :271-284
[33]   CONSTRUCTION OF SPECIAL EDGE-COLORINGS [J].
BRASS, P ;
MENGERSEN, I .
UTILITAS MATHEMATICA, 1989, 36 :201-210
[34]   HOMOGENEOUS EDGE-COLORINGS OF GRAPHS [J].
Bonacini, Paola ;
Cinquegrani, Maria Grazia ;
Marino, Lucia .
UTILITAS MATHEMATICA, 2016, 100 :269-276
[35]   Maximal Edge-Colorings of Graphs [J].
Mariusz Meszka ;
Magdalena Tyniec .
Graphs and Combinatorics, 2017, 33 :1451-1458
[36]   On star and biclique edge-colorings [J].
Dantas, Simone ;
Groshaus, Marina ;
Guedes, Andre ;
Machado, Raphael C. S. ;
Ries, Bernard ;
Sasaki, Diana .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2017, 24 (1-2) :339-346
[37]   Extending edge-colorings of complete hypergraphs into regular colorings [J].
Bahmanian, Amin .
JOURNAL OF GRAPH THEORY, 2019, 90 (04) :547-560
[38]   Simple reduction of f-colorings to edge-colorings [J].
Zhou, X ;
Nishizeki, T .
COMPUTING AND COMBINATORICS, 1995, 959 :223-228
[39]   Edge-Colorings with No Large Polychromatic Stars [J].
Tao Jiang .
Graphs and Combinatorics, 2002, 18 :303-308
[40]   Normal edge-colorings of cubic graphs [J].
Mazzuoccolo, Giuseppe ;
Mkrtchyan, Vahan .
JOURNAL OF GRAPH THEORY, 2020, 94 (01) :75-91