全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2013 

Independence and Matching Number in Graphs with Maximum Degree 4

Full-Text   Cite this paper   Add to My Lib

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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133