Independent sets and matchings in subcubic graphs

We prove that every graph G of maximum degree at most 3 satisfies 32α(G)+ ^α′(G)+12t(G)<n(G), where α(G) is the independence number of G, ^α′(G) is the matching number of G, and t(G) denotes the maximum number of vertex disjoint triangles in G. As a special case, every triangle-free graph G of maximum degree at most 3 satisfies 32α(G)+ ^α′(G)<n(G). This inequality is best possible and confirms a recent conjecture posed by Pedersen. Furthermore, it implies χ(G)≤32ω(G) for every 3 ^K1, ^K1∪ ^K4-free graph G, where χ(G) is the chromatic number of G and ω(G) is the clique number of G, which solves a recent problem posed by Choudum et al. [S.A. Choudum, T. Karthick, M.A. Shalu, Linear chromatic bounds for a subfamily of 3 ^K1-free graphs, Graphs Combin. 24 (2008) 413-428]. Finally, we prove a best possible lower bound on the matching number of connected cubic graphs in terms of their order and odd girth, and characterize all extremal graphs.