On the Subspace Choosability in Graphs

Abstract

A graph $G$ is said to be $k$-subspace choosable over a field $F$ if for every assignment of $k$-dimensional subspaces of some finite-dimensional vector space over $F$ to the vertices of $G$, it is possible to choose for each vertex a nonzero vector from its subspace so that adjacent vertices receive orthogonal vectors over $F$. The subspace choice number of $G$ over $F$ is the smallest integer $k$ for which $G$ is $k$-subspace choosable over $F$. This graph parameter, introduced by Haynes, Park, Schaeffer, Webster, and Mitchell (Electron. J. Comb., 2010), is inspired by well-studied variants of the chromatic number of graphs, such as the (color) choice number and the orthogonality dimension.

We study the subspace choice number of graphs over various fields. We first prove that the subspace choice number of every graph with average degree $d$ is at least $\Omega(\sqrt{d/\ln d})$ over any field. We then focus on bipartite graphs and consider the problem of estimating, for a given integer $k$, the smallest integer $m$ for which the subspace choice number of the complete bipartite graph $K_{k,m}$ over a field $F$ exceeds $k$. We prove upper and lower bounds on this quantity as well as for several extensions of this problem. Our results imply a substantial difference between the behavior of the choice number and that of the subspace choice number. We also consider the computational aspect of the subspace choice number, and show that for every $k \geq 3$ it is $NP$-hard to decide whether the subspace choice number of a given bipartite graph over $F$ is at most $k$, provided that $F$ is either the real field or any finite field.