𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On an anti-Ramsey problem of Burr, Erdős, Graham, and T. Sós

✍ Scribed by Gábor N. Sárközy; Stanley Selkow

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
98 KB
Volume
52
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a graph L, in this article we investigate the anti‐Ramsey number χ~S~(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC).

In 7 among many other interesting results and problems, Burr, Erdős, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that

In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006

📜 SIMILAR VOLUMES

On a Problem of Erdős and Sárközy
On a Problem of Erdős and Sárközy
✍ Tomasz Schoen 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 89 KB

Let A=[a 1 , a 2 , ...] N and put A(n)= a i n 1. We say that A is a P-set if no element a i divides the sum of two larger elements. It is proved that for every P-set A with pairwise co-prime elements the inequality A(n)<2n 2Â3 holds for infinitely many n # N. ## 2001 Academic Press where A(n)= a i

On A Problem of Erdős and Turán and Some
On A Problem of Erdős and Turán and Some Related Results
✍ N. Alon; M.N. Kolountzakis 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 315 KB

We employ the probabilistic method to prove a stronger version of a result of Helm, related to a conjecture of Erdos and Turan about additive bases of the positive integers. We show that for a class of random sequences of positive integers \(A\), which satisfy \(|A \cap[1, x]| \gg \sqrt{x}\) with pr

On an Inequality of Erdős and Turán Conc
On an Inequality of Erdős and Turán Concerning Uniform Distribution Modulo One, II
✍ I.Z. Ruzsa 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 126 KB

A famous inequality of Erdös and Turán estimates the discrepancy \(\Delta\) of a finite sequence of real numbers by the quantity \(B=\min _{K} K^{-1}+\sum_{k=1}^{K-1}\left|\alpha_{k}\right| / k\), where the \(\alpha_{k}\) are the Fourier coefficients. We investigate how bad this estimate can be. We

Probability Galore. Review of The Probab
Probability Galore. Review of The Probabilistic Method, by Noga Alon and Joel H. Spencer, with an appendix on open problems by Paul Erdös
✍ Peter Fishburn 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Noga Alon is a Professor of Mathematics at Tel Aviv University, Israel. He received his Ph.D. in mathematics from the Hebrew University of Jerusalem in 1983 and has had visiting positions in various rescarch institutes including MIT, IBM Almaden Research Center, Bell Laboratories, and Beflcore. He s