caa a22 4500 475778227 CHVBK 20180406123637.0 cr unu---uuuuu 170329e20000601xx s 000 0 eng 10.1007/PL00021175 doi (NATIONALLICENCE)springer-10.1007/PL00021175 Abbasi Sarmad Department of Computer Science, Quaid-i-Azam University, Islamabad 45320, Pakistan, PK aut How Tight Is the Bollobás-Komlós Conjecture? [Elektronische Daten] [Sarmad Abbasi] Abstract.: The bipartite case of the Bollobás and Komlós conjecture states that for every Δ0, γ>0 there is an α=α(Δ0, γ) >0 such that the following statement holds: If G is any graph with minimum degree at least then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶ ¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v 1, ..., v n such that v i∼H v j implies |i−j|≤b.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as γ→0 then α→0. More precisely, we show that for any there is a Δ0 such that that α(Δ0, γ)≤4 γ. Springer-Verlag Tokyo, 2000 https://doi.org/10.1007/PL00021175 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00021175 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Abbasi Sarmad Department of Computer Science, Quaid-i-Azam University, Islamabad 45320, Pakistan, PK aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer