Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The competition number of a graph and the dimension of its hole space   The competition graph of a digraph D is a (simple undirected) graph which has
the same vertex set as D and has an edge between x and y if and only if there
exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph
G, G together with sufficiently many isolated vertices is the competition graph
of some acyclic digraph. The competition number k(G) of G is the smallest
number of such isolated vertices. In general, it is hard to compute the
competition number k(G) for a graph G and it has been one of 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 is being 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 no 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.

20
The categories of this paper are: acc-phys
1
The categories of this paper are: cs
27
The categories of this paper are: comp-gas
24
The categories of this paper are: dg-ga
25
The categories of this paper are: patt-sol
29
The categories of this paper are: funct-an
12
The categories of this paper are: nucl-th
36
The categories of this paper are: cmp-lg
22
The categories of this paper are: chao-dyn
11
The categories of this paper are: hep-lat
23
The categories of this paper are: solv-int
3
The categories of this paper are: physics
37
The categories of this paper are: supr-con
21
The categories of this paper are: adap-org
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph