New Bound for Classical Zero-Error Capacity using Partially Commutative Monoids as Counting Tools

In this paper we propose a new bound for the classical zero-error capacity of a communication channel using partially commutative monoids as enumeration tools. Specifically, we analyze the relationship between classical zero-error capacity and the growth factor of the monoid, \(\beta(G)\), of a graph \(G\). Although the value of \(\beta(G)\) allows us to calculate an upper bound for the classical zero-error capacity, determining it requires counting the number of cliques in a graph, which is an NP-Complete problem. Our main result is that the classical zero-error capacity is always lower than the integer part of \(\beta(G)\).