Independent sets and matchings in subcubic graphs

We prove that every graph G of maximum degree at most  3 satisfies 3 2 α ( G ) + α ′ ( G ) + 1 2 t ( 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 3 2 α ( G ) + α ′ ( G ) ≥ n ( G ) . This inequality is best possible and confirms a recent conjecture posed by Pedersen. Furthermore, it implies χ ( G ) ≤ 3 2 ω ( G ) for every { 3 K 1 , K 1 ∪ K 4 } -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 K 1 -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.