  We study the problem of communicating over a discrete memoryless two-way
channel using non-adaptive schemes, under a zero probability of error
criterion. We derive single-letter inner and outer bounds for the zero-error
capacity region, based on random coding, linear programming, linear codes, and
the asymptotic spectrum of graphs. Among others, we provide a single-letter
outer bound based on a combination of Shannon's vanishing-error capacity region
and a two-way analogue of the linear programming bound for point-to-point
channels, which in contrast to the one-way case, is generally better than both.
Moreover, we establish an outer bound for the zero-error capacity region of a
two-way channel via the asymptotic spectrum of graphs and show that this bound
could be achieved for certain cases.
