Bipartite subgraphs of triangle-free subcubic graphs

Suppose G is a graph with n vertices and m edges. Let n′ be the maximum number of vertices in an induced bipartite subgraph of G and let m′ be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G)=m′/m is called the bipartite density of G, and b∗(G)=n′/n is called the bipartite ratio of G. This paper proves that every 2-connected triangle-free subcubic graph, apart from seven exceptions, has b(G)⩾17/21. Every 2-connected triangle-free subcubic graph other than the Petersen graph and the dodecahedron has b∗(G)⩾5/7. The bounds that b∗(G)⩾5/7 and b(G)⩾17/21 are tight in the sense that there are infinitely many 2-connected triangle-free cubic graphs G for which b(G)=17/21 and b∗(G)=5/7. On the other hand, if G is not cubic (i.e., G have vertices of degree at most 2), then the strict inequalities b∗(G)>5/7 and b(G)>17/21 hold, with a few exceptions. Nevertheless, the bounds are still sharp in the sense that for any ϵ>0, there are infinitely many 2-connected subcubic graphs G with minimum degree 2 such that b∗(G)<5/7+ϵ and b(G)<17/21+ϵ. The bound that b(G)⩾17/21 is a common improvement of an earlier result of Bondy and Locke and a recent result of Xu and Yu: Bondy and Locke proved that every triangle-free cubic graph other than the Petersen graph and the dodecahedron has b(G)>4/5. Xu and Yu confirmed a conjecture of Bondy and Locke and proved that every 2-connected triangle free subcubic graph with minimum degree 2 apart from five exceptions has b(G)>4/5. The bound b∗(G)⩾5/7 is a strengthening of a well-known result (first proved by Fajtlowicz and by Staton, and with a few new proofs found later) which says that any triangle-free subcubic graph G has independence ratio at least 5/14. The proofs imply a linear time algorithm that finds an induced bipartite subgraph H of G with |V(H)|/|V(G)|⩾5/7 and a spanning bipartite subgraph H′ of G with |E(H′)|/|E(G)|⩾17/21.