Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T09:11:33.356Z Has data issue: false hasContentIssue false
  • English
  • Français

Bipartite Coverings of Graphs

Published online by Cambridge University Press:  01 September 1997

VOJTECH RÖDL  and
ANDRZEJ RUCIŃSKI
VOJTECH RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta GA 30322, USA (e-mail: rodl@mathcs.emory.edu)
ANDRZEJ RUCIŃSKI
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta GA 30322, USA (e-mail: rodl@mathcs.emory.edu) Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland (e-mail: rucinski@math.amu.edu.pl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this note we give a probabilistic proof of the existence of an n-vertex graph Gn, n=1, 2, [ctdot ], such that, for some constant c>0, the edges of Gn cannot be covered by n−c log n complete bipartite subgraphs of Gn. This result improves a previous bound due to F. R. K. Chung and is the best possible up to a constant.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 3 , September 1997 , pp. 349 - 352
Copyright
1997 Cambridge University Press