Edge-colorings avoiding rainbow stars

被引：2

作者：

Hoppen, Carlos ^{[1
]}

Lefmann, Hanno ^{[2
]}

Odermann, Knut ^{[2
]}

Sanches, Juliana ^{[1
]}

机构：

[1] Univ Fed Rio Grande do Sul, Inst Matemat & Estat, Ave Bento Goncalves 9500, BR-91501970 Porto Alegre, RS, Brazil

[2] Tech Univ Chemnitz, Fak Informat, Str Nationen 62, D-09107 Chemnitz, Germany

来源：

JOURNAL OF GRAPH THEORY | 2018年 / 87卷 / 04期

关键词：

extremal graph theory; edge-colorings; NUMBER; GRAPHS;

D O I：

10.1002/jgt.22165

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider an extremal problem motivated by a article of Balogh [J.Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565-573], who considered edge-colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given rt2, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t-1 colors appear in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-colored stars with t edges. For large n, we show that, with the exception of the case t=2, the complete graph Kn is always the unique extremal graph. We also consider generalizations of this problem.

引用

页码：399 / 429

页数：31

共 18 条

[1] The number of edge colorings with no monochromatic cliques [J].