The inertia–bicoloring conjecture for full-rank typical graphs

Let $G$ be a full-rank typical graph. A $G$-partial matrix is a partial symmetric matrix whose specified off-diagonal entries correspond to the edges of $G$; it is minimally completable to full rank if it has a completion of full rank but no proper submatrix obtained by deleting a specified entry has this property. Write $G^c$ for the complement of $G$, and let $\operatorname{In}(M)=(m,n,0)$ denote the common inertia of all completions of $M$, with $m$ positive and $n$ negative eigenvalues. A proper bicoloring of $G^c$ assigns red or blue to every vertex so that adjacent vertices have different colors. Inertia–bicoloring conjecture. There exists a $G$-partial matrix $M$, minimally completable to full rank, with $\operatorname{In}(M)=(m,n,0)$ if and only if $G^c$ has a proper bicoloring with $m$ red vertices and $n$ blue vertices. The conjecture characterizes the possible inertias of minimally full-rank-completable partial matrices in terms of proper two-colorings of the complement. The stated evidence is that the authors found no full-rank typical graph and corresponding partial matrix whose inertia failed to arise from such a coloring; the general characterization remains open.