首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Largest bipartite subgraphs in triangle-free graphs with maximum degree three
Authors:J A Bondy  S C Locke
Abstract:Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomial algorithm which returns a bipartite subgraph of G containing at least ? of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, connected graphs for which no bipartite subgraph has more than this proportion.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号