BIPARTITE SUBGRAPHS OF TRIANGLE-FREE GRAPHS

作     者：POLJAK, S TUZA, Z 

作者机构：HUNGARIAN ACAD SCIINST COMP & AUTOMATH-1111 BUDAPESTHUNGARY 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1994年第7卷第2期

页      面：307-313页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：TRIANGLE-FREE GRAPH MAXIMUM BIPARTITE SUBGRAPH POLYNOMIAL-TIME ALGORITHM 

摘      要：The authors present a lower bound on the maximum size of a bipartite subgraph of a triangle-free graph that improves a result due to Erdos and Lovasz. It also gives a polynomial-time algorithm, while the previous bound was proved by probabilistic methods.