Abstract
When adjacency of graph vertices represents confusability of code symbols in a communication link, the graph capacity represents the highest rate achievable by zero-error codes. We consider a variation of the problem where the noise can only affect a fraction delta of the symbols and ask for the highest achievable rate of zero-error codes subject to this additional assumption. We present some Gilbert-Varshamov-like achievability results and a converse based on Delsarte linear programming bound. Improved bounds on the reliability function of some discrete memoryless channels are derived as an application of these results.