The Haemers number of an -vertex graph , denoted , (Alipour abd Gohari 2023), or (Haemers 1978), is an integer defined as the minimum rank over all matrices over some field such that and if vertices and are not adjacent in a given graph . (Note that the critical word "not" was inadvertently omitted in the original Haemers (1978) paper.)
The Haemers number provodes upper bound on the Shannon capacity of which is sometimes better than the Lovász number.
The Haemers number satisfies
(Haemers 1978), where is the chromatic number and denotes the graph complement of .