Independent sets and matchings in subcubic graphs

AbstractWe 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 {3K1,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 3K1-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