The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913867557240832 |
|---|---|
| author | Barioli, Francesco Fallat, Shaun M. Gupta, Himanshu Li, Zhongshan |
| author_facet | Barioli, Francesco Fallat, Shaun M. Gupta, Himanshu Li, Zhongshan |
| contents | Since the transformative workshop by the American Institute of Mathematics on the minimum rank of a graph, two longstanding open problems have captivated the community interested in the minimum rank of graphs: the graph complement conjecture and the $δ$-conjecture. In this paper, we use a classical result of Mader (1972) to establish a weak version of the graph complement conjecture for all key minimum rank parameters. In addition, again using the same result of Mader, we present some extremal resolutions of the $δ$-conjecture. Furthermore, we incorporate the assumption of the $δ$-conjecture and extensive work on graph degeneracy to improve the bound in the weak version of the graph complement conjecture. We conclude with a list of conjectured bounds on the positive semidefinite variant of the Colin de Verdière number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24577 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture Barioli, Francesco Fallat, Shaun M. Gupta, Himanshu Li, Zhongshan Combinatorics 05C50, 15A03, 05C35 Since the transformative workshop by the American Institute of Mathematics on the minimum rank of a graph, two longstanding open problems have captivated the community interested in the minimum rank of graphs: the graph complement conjecture and the $δ$-conjecture. In this paper, we use a classical result of Mader (1972) to establish a weak version of the graph complement conjecture for all key minimum rank parameters. In addition, again using the same result of Mader, we present some extremal resolutions of the $δ$-conjecture. Furthermore, we incorporate the assumption of the $δ$-conjecture and extensive work on graph degeneracy to improve the bound in the weak version of the graph complement conjecture. We conclude with a list of conjectured bounds on the positive semidefinite variant of the Colin de Verdière number. |
| title | The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture |
| topic | Combinatorics 05C50, 15A03, 05C35 |
| url | https://arxiv.org/abs/2505.24577 |