Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647893 | Discrete Mathematics | 2012 | 5 Pages |
Abstract
A hole of a graph GG is an induced cycle of length at least 4. Kim (2005) [3] conjectured that the competition number k(G)k(G) is bounded by h(G)+1h(G)+1 for any graph GG, where h(G)h(G) is the number of holes of GG. Li and Chang (2009) [5] proved that the conjecture is true for a graph whose holes all satisfy a property called ‘independence’. In this paper, by using similar proof techniques in Li and Chang (2009) [5], we prove the conjecture for graphs satisfying two conditions that allow the holes to overlap a lot.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Akira Kamibeppu,