Anti-Ramsey 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 edge-colorings of complete graphs, quo vadis, graph theory? Ann. Discrete Math. 55, (1993), 81-88. |
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), 7-9.
|