BIPARTITE SUBGRAPHS OF TRIANGLE-FREE GRAPHS

Authors
POLJAK S TUZA Z
Citation
S. Poljak et Z. Tuza, BIPARTITE SUBGRAPHS OF TRIANGLE-FREE GRAPHS, SIAM journal on discrete mathematics, 7(2), 1994, pp. 307-313
Citations number
15
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
7
Issue
2
Year of publication
1994
Pages
307 - 313
Database
ISI
SICI code
0895-4801(1994)7:2<307:BSOTG>2.0.ZU;2-7
Abstract
The authors present a lower bound on the maximum size of a bipartite s ubgraph of a triangle-free graph that improves a result due to Erdos a nd Lovasz. It also gives a polynomial-time algorithm, while the previo us bound was proved by probabilistic methods.