Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423364 | Discrete Mathematics | 2014 | 6 Pages |
Abstract
We prove that 74α(G)+β(G)â¥n(G) and α(G)+32β(G)â¥n(G) for every triangle-free graph G with maximum degree at most 4, where α(G) is the independence number and β(G) is the matching number of G, respectively. These results are sharp for a graph on 13 vertices. Furthermore we show Ï(G)â¤74Ï(G) for {3K1,K1âªK5}-free graphs, where Ï(G) is the chromatic number and Ï(G) is the clique number of G, respectively.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Felix Joos,