AntiRamsey problem for balanced colorings
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Problem (proposed by Erdös and Tuza [1])
Let \(G\) denote a given graph on \(e\) edges. Suppose the edges of a complete graph on \(n\) vertices are colored in \(e+1\) colors so that at every vertex each color occurs at least \((1\epsilon)n/(e+1)\) times. Is it true that there is a subgraph isomorphic to \(G\) with all edges in different colors?The special case when \( H\) is a triangle is well understood. However, for other graphs, the problem remains open [1][2] even for \( d\)regular colorings when \( n=de+1\).
Bibliography  

1  P. Erdös and Z. Tuza, Rainbow subgraphs in edgecolorings of complete graphs, quo vadis, graph theory? Ann. Discrete Math. 55, (1993), 8188. 
2 
P. Erdös,
Some of my favourite problems on cycles and colourings,
Cycles and colourings '94
Stará Lesná, 1994,
Tatra Mt. Math. Publ. 9 (1996), 79.
