  The index coding problem studies the fundamental limit on broadcasting
multiple messages to their respective receivers with different sets of side
information that are represented by a directed graph. The generalized
lexicographic product structure in the side information graph is introduced as
a natural condition under which the corresponding index coding problem can be
decomposed into multiple interacting subproblems. The capacity region is
characterized in terms of the subproblem capacity regions combined in the same
product structure. The proof is based on dual uses of random coding---one for a
new multiletter characterization of the capacity region of a general index
coding problem via joint typicality decoding and the other for a construction
of a new multiletter code of matching rates from a single-letter code via joint
typicality encoding. Several special cases are discussed that recover and
strengthen known structural properties of the index coding capacity region.
