  In this paper we define critical graphs as minimal graphs that support a
given set of rates for the index coding problem, and study them for both the
one-shot and asymptotic setups. For the case of equal rates, we find the
critical graph with minimum number of edges for both one-shot and asymptotic
cases. For the general case of possibly distinct rates, we show that for
one-shot and asymptotic linear index coding, as well as asymptotic non-linear
index coding, each critical graph is a union of disjoint strongly connected
subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for
a one-shot non-linear index coding problem. Next, we identify a few graph
structures that are critical. We also generalize some of our results to the
groupcast problem. In addition, we show that the capacity region of the index
coding is additive for union of disjoint graphs.
