Independence and Matching Number in Graphs with Maximum Degree 4

Abstract

We prove that $\frac{7}{4}\alpha (G)+\beta (G)\ge n(G)$ and $\alpha (G)+\frac{3}{2}\beta (G)\ge n(G)$ for every triangle-free graph $G$ with maximum degree at most $4$, where $\alpha (G)$ is the independence number and $\beta (G)$ is the matching number of $G$, respectively. These results are sharp for a graph on $13$ vertices. Furthermore we show $\chi (G)\le \frac{7}{4}\omega (G)$ for $\{3K_1,K_1\cup K_5\}$-free graphs, where $\chi (G)$ is the chromatic number and $\omega (G)$ is the clique number of $G$, respectively.

arXiv comment9 pages