A sufficient condition for Kim’s conjecture on the competition numbers of graphs

A hole of a graph G is an induced cycle of length at least 4. Kim (2005) [3] conjectured that the competition number k ( G ) is bounded by h ( G ) + 1 for any graph G , where h ( G ) is the number of holes of G . 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.