This thesis concerns error-free communication channels from a graph-theoretic viewpoint, first described by Shannon with the Θ(G)-function in 1956. In this thesis, we undertake a detailed mathematical and historical walk-through and synthesis of fundamental contributions to this field. Approaching the main goal of describing the behavior and exact values for the maximum error-free capacity of a channel Θ(G), this thesis first re-establishes in depth the basic concepts of linear programming to explain early bounds given for Θ(G). The core of this thesis presents a general bound of Θ(G) with ϑ(G), a function invented by Lovász in 1979. Finally, analytical formulas for ϑ(G) are proven for graphs exhibiting specific structural properties. The state of research can be summarized as follows: The general bound Θ(G) ≤ϑ(G) in special families of graphs like cycles, regular, or perfect graphs is often precise and well-studied, but definite values for Θ(G) are only known for a handful of examples.Finding these values remains an open problem in mathematics and information theory; furthermore, a paper published on 3 July 2025 has proven that the zero-error capacity of noisy channels is not Banach–Mazur-computable and therefore also not Borel–Turing-computable.