Independent sets and matchings in subcubic graphs

We prove that every graph GG of maximum degree at most 33 satisfies 32α(G)+α′(G)+12t(G)≥n(G), where α(G)α(G) is the independence number of GG, α′(G)α′(G) is the matching number of GG, and t(G)t(G) denotes the maximum number of vertex disjoint triangles in GG. As a special case, every triangle-free graph GG of maximum degree at most 33 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 {3K1,K1∪K4}{3K1,K1∪K4}-free graph GG, where χ(G)χ(G) is the chromatic number of GG and ω(G)ω(G) is the clique number of GG, 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 3K13K1-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.