A chromatic lower bound for positive-semidefinite nullity with SAP
For a finite simple graph $G$ on the vertex set $\{1, \dots, n\}$, $n \ge 1$, let $\mathcal S(G)$ be the set of real symmetric $n \times n$ matrices $A$ such that, for $i \ne j$, $a_{ij} \ne 0$ exactly when $\{i, j\}$ is an edge of $G$, the diagonal being unrestricted. A real symmetric $n \times n$ matrix $A$ has the strong Arnold property if the only real symmetric $X$ with $AX = 0$, $A \circ X = 0$ and $I_n \circ X = 0$ is $X = 0$, where $\circ$ is the entrywise product. Let $\nu(G)$, the parameter Colin de Verdière introduced in 1998, be the largest nullity of a positive semidefinite $A \in \mathcal S(G)$ with the strong Arnold property, and let $\chi(G)$ be the chromatic number of $G$. Every graph has a subgraph of minimum degree at least $\chi(G) - 1$ and $\nu$ is minor monotone, so, as Barioli, Fallat, Gupta and Li note, the bound below would follow from the conjecture of Barioli et al. (2013) that $\nu(G) \ge \delta(G)$, the minimum degree of $G$. It would also follow from Hadwiger's conjecture, since $\nu(G) \ge \eta(G) - 1$ for the Hadwiger number $\eta(G)$. Barioli, Fallat, Gupta and Li proved $\nu(G) > 16\chi(G)/49$.
Problem. Is $\nu(G) \ge \chi(G) - 1$ for every $n \ge 1$ and every graph $G$ on $n$ vertices?
Source: Barioli, Fallat, Gupta and Li (2026; arXiv 2025), Conjecture 4.1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NA, SP
- Keywords
- Colin de Verdière parameters, graph colorings, OpenProblemsInNLA, strong Arnold property
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{barioli2026,
author = {Barioli, Francesco and Fallat, Shaun M. and Gupta, Himanshu and Li, Zhongshan},
title = {The weak version of the graph complement conjecture and partial results for the delta conjecture},
journal = {Discrete Math.},
volume = {349},
number = {3},
year = {2026},
pages = {114861},
doi = {10.1016/j.disc.2025.114861},
eprint = {2505.24577},
archivePrefix = {arXiv},
}
@article{barioli2013,
author = {Barioli, Francesco and Barrett, Wayne and Fallat, Shaun M. and Hall, H. Tracy and Hogben, Leslie and Shader, Bryan and van den Driessche, P. and van der Holst, Hein},
title = {Parameters related to tree-width, zero forcing, and maximum nullity of a graph},
journal = {J. Graph Theory},
volume = {72},
number = {2},
year = {2013},
pages = {146--177},
doi = {10.1002/jgt.21637},
}
@article{colindeverdiere1998,
author = {Colin de Verdi{\`e}re, Yves},
title = {Multiplicities of eigenvalues and tree-width of graphs},
journal = {J. Combin. Theory Ser. B},
volume = {74},
number = {2},
year = {1998},
pages = {121--146},
doi = {10.1006/jctb.1998.1834},
}
@misc{openproblemsinnla-sp12,
author = {Townsend, Alex},
title = {{SP-12}: A chromatic lower bound for positive-semidefinite nullity with SAP},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/SP-12/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
In 1987 Hiroshi Maehara conjectured that a graph can be represented by vectors considered adjacent when not orthogonal (a faithful orthogonal representation) in codimension the minimum degree of the graph. Without settling the conjecture, Làslò Lovàsz, Michael Saks, and Alexander Schrijver (LSS) showed that a codimension of vertex connectivity both suffices and is best possible under the additional assumption of …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00253, "A chromatic lower bound for positive-semidefinite nullity with SAP", clopen.solutions.