Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419746 | Discrete Applied Mathematics | 2009 | 5 Pages |
Abstract
A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph GG is defined as b(G)=max{|E(B)|/|E(G)|:Bb(G)=max{|E(B)|/|E(G)|:B is a bipartite subgraph of G}G}. It was conjectured by Bondy and Locke that if GG is a triangle-free subcubic graph, then b(G)≥45 and equality holds only if GG is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xuding Zhu,