On Some Problems of Lovász Concerning the Shannon Capacity of a Graph

DOI10.1109/TIT.1979.1056027MaRDI QIDQ4187729zbMATH OpenOpenAlexWikidataFDO

Authors Willem H. Haemers

Publication date 1979

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.1979.1056027

zbMATH Keywords

Shannon Capacity of a Graph

Mathematics Subject Classification ID

Graph theory (05C99) Communication, information (94A99)

Cited in

(36)

• A bound on the Shannon capacity via a linear programming variation
• On the Shannon capacity of sums and products of graphs
• Entanglement can increase asymptotic rates of zero-error classical communication over classical channels
• A new property of the Lovász number and duality relations between graph parameters
• On minrank and forbidden subgraphs
• On the independence numbers of the cubes of odd cycles
• Applications of Ramsey theory
• Approximation of the Shannon capacity via matrix cone programming
• Semidefinite programming for discrete optimization and matrix completion problems
• New lower bounds for the Shannon capacity of odd cycles
• Linear index coding via semidefinite programming
• On the subspace choosability in graphs
• Topological bounds for graph representations over any field
• Independent sets in graphs
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Shannon capacity and the categorical product
• Graph information ratio
• A limit theorem for the Shannon capacities of odd cycles I
• Orthogonal representations over finite fields and the chromatic number of graphs
• A unified construction of semiring-homomorphic graph invariants
• A combinatorial approach to nonlocality and contextuality
• Improved incidence bounds over arbitrary finite fields via the VC-dimension theory
• The zero-error capacity of binary channels with 2-memories
• The hat guessing number of graphs
• Faithful orthogonal representations of graphs from partition logics
• On minrank and the Lovász theta-function
• Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
• The Sperner capacity of linear and nonlinear codes for the cyclic triangle
• On the normalized Shannon capacity of a union
• Linear index coding via semidefinite programming
• Probabilistic refinement of the asymptotic spectrum of graphs
• Capacities: From information theory to extremal set theory
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• New lower bound on the Shannon capacity of \(C_7\) from circular graphs
• The minrank of random graphs
• Analytical properties of Shannon's capacity of arbitrarily varying channels under list decoding: super-additivity and discontinuity behavior

This page was built for publication: On Some Problems of Lovász Concerning the Shannon Capacity of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4187729)