Vector Chromatic Number

The vector chromatic number of a simple graph containing an edge is the least real for which its vertices can be assigned unit vectors satisfying

The dimension of the vectors is unrestricted, and denotes the inner product. This is a relaxation of the chromatic number introduced by Karger et al. (1998).

A vertex coloring with colors gives such vectors by assigning the vertices of a regular -simplex centered at the origin to the colors. Consequently,

where is the clique number and the chromatic number. In particular, a complete graph has value , and a bipartite graph containing an edge has value 2.

For a graph with edges, Balla et al. (2024) bound the size of a maxcut below by . Juliano (2026) proves the constant is best possible.