The competition number of a graph and the dimension of its hole space

The competition graph of a digraph DD is a (simple undirected) graph which has the same vertex set as DD and has an edge between xx and yy if and only if there exists a vertex vv in DD such that (x,v)(x,v) and (y,v)(y,v) are arcs of DD. For any graph GG, GG together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G)k(G) of GG is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G)k(G) for a graph GG and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.