ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

On a bottleneck bipartition conjecture of Erdős (1992)

Porter, T. D.

Springer

Combinatorica 12 (1992), S. 317-321

add to mindlist on the mindlist

Details

ISSN: 1439-6912

Keywords: 05 C 35

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract For a graphG, let γ(U,V)=max{e(U), e(V)} for a bipartition (U, V) ofV(G) withUυV=V(G),UφV=Ø. Define γ(G)=min(U,V ){γ(U,V)}. Paul Erdős conjectures $$\gamma (G)/e(G) \leqslant {1 \mathord{\left/ {\vphantom {1 4}} \right. \kern-\nulldelimiterspace} 4} + O\left( {1/\sqrt {e(G)} } \right)$$ . This paper verifies the conjecture and shows $$\gamma (G)/e(G) \leqslant {1 \mathord{\left/ {\vphantom {1 4}} \right. \kern-\nulldelimiterspace} 4}\left( {1 + \sqrt {2/e(G)} } \right)$$ .

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01285820

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit