## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1900-1910 |

Number of pages | 11 |

Journal | Discrete Mathematics |

Volume | 312 |

Issue number | 11 |

DOIs | |

Publication status | Published - 6 Jun 2012 |

## Keywords

- Chromatic number
- Independence number
- Matching number
- χ-binding function

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics