How to make a graph bipartite
How to make a graph bipartite
复制标题
如何制作二分图
DOI：
10.1016/0095-8956(88)90057-3
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
P. Erdös;R. Faudree;J. Pach;J. Spencer
定理1.对任意n个顶点m条边的无三角形图G，最多可通过省略（m2 m（2 m2 - 13）4 m2 j min S1，tt 2 n2（n '-2 rn），n12条边而使其成为二部图.
THEOREM 1. Every triangle free graph G with n vertices and m edges can be made bipartite by the omission of at most (m 2m (2m 2-1 3) 4m 2 j min S l, tt 2 n2 (n'-2rn), n 12 edges.