Paper Info
Title
On an anti-Ramsey property of Ramanujan graphs
Abstract
If G and H are graphs, we write G→ H (respectively, G→ TH) if for any proper edge‐coloring γ of G there is a subgraph H' ⊂ G of G isomorphic to H (respectively, isomorphic to a subdivision of H) such that γ is injective on E(H'). Let us write Cl for the cycle of length l. Spencer (cf. Erdös 10]) asked whether for any g ⩾ 3 there is a graph G = Gg such that (i) G has girth g(G) at least g and (ii) G→ TC3. Recently, Rödl and Tuza [22] answered this question in the affirmative by proving, using nonconstructive methods, a result that implies that, for any t ⩾ 1, there is a graph G = Gt of girth t + 2 such that G→ C2t+2. In particular, condition (ii) may be strengthened to (iii) G→ C𝓁 for some l = 𝓁(G). For G = Gt above 𝓁 = 𝓁(G) = 2t + 2 = 2g(G) − 2. Here, we show that suitable Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak [18] are explicit examples of graphs G = Gg satisfying (i) and (iii) above. For such graphs, 𝓁 = l(G) in (iii) may be taken to be roughly equal to (3/2)g(G), thus considerably improving the value 2g(G) − 2 given in the result of Rödl and Tuza. It is not known whether there are graphs G of arbitrarily large girth for which (iii) holds with 𝓁 = 𝓁(G) = g(G). © 1995 Wiley Periodicals, Inc.
Year
DOI
Venue
1995
10.1002/rsa.3240060405
Random Structures & Algorithms
Keywords
DocType
Volume
anti-ramsey property,wiley periodicals,g isomorphic,graphs g,ramanujan graph,ramsey property,suitable ramanujan graph,explicit example,subgraph h,graph g,large girth,girth g,length l
Journal
6
Issue
ISSN
Citations 
4
1042-9832
3
PageRank 
References 
Authors
0.49
12
2
Name
Order
Citations
PageRank
P. E. Haxell121226.40
Yoshiharu Kohayakawa217222.74