Monochromatic Vs multicolored paths
1992; Springer Science+Business Media; Volume: 8; Issue: 4 Linguagem: Inglês
10.1007/bf02351589
ISSN1435-5914
AutoresHanno Lefmann, Vojtěch Rödl, Robin Thomas,
Tópico(s)Advanced Graph Theory Research
ResumoLetl andk be positive integers, and letX={0,1,...,l k−1}. Is it true that for every coloring δ:X×X→{0,1,...} there either exist elementsx 0<x 1<...<x l ofX with δ(x 0,x 1)=δ(x 1,x 2)=...=δ(x l−1,x l), or else there exist elementsy 0<y 1<...<y k ofX with δ(y i−1,y i) ∈ δ(y j−1,y j) for all 1<-i<j≤k? We prove here that this is the case if eitherl≤2, ork≤4, orl≥(3k)2k . The general question remains open.
Referência(s)