pith. sign in

arxiv: 1312.0407 · v1 · pith:PMGH2RZFnew · submitted 2013-12-02 · 🧮 math.CO

Independence and Matching Number in Graphs with Maximum Degree 4

classification 🧮 math.CO
keywords numberalphabetafracdegreegraphgraphsindependence
0
0 comments X
read the original abstract

We prove that $\frac{7}{4}\alpha(G)+\beta(G)\geq n(G)$ and $\alpha(G)+\frac{3}{2}\beta(G)\geq 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)\leq \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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.