The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture

Francesco Barioli; Himanshu Gupta; Shaun M. Fallat; Zhongshan Li

The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture

T0 review · 0 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves a universal bound below 1.708n for the minimum-rank sum of a graph and its complement, settling the weak graph complement conjecture for all key parameters.

desk verdict Mader's theorem gives a clean proof of the weak graph complement conjecture with constant 1+1/sqrt(2), plus a full degeneracy-pair characterization; the paper is solid and deserves refereeing. read the letter →

arxiv 2505.24577 v1 pith:CD4NMMAR submitted 2025-05-30 math.CO

Francesco Barioli , Shaun M. Fallat , Himanshu Gupta , Zhongshan Li This is my paper

classification math.CO MSC 05C5015A0305C35

keywords minimumrankmaximumnullitystrongArnoldpropertygraphcomplementconjecturedeltaMader'stheoremdegeneracyNordhaus-Gaddum

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that for every graph $G$ on $n\ge 4$ vertices, $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) < (1+1/\sqrt2)n+1$, where $\operatorname{mr}_\nu(G)=n-\nu(G)$ and $\nu(G)$ is the maximum positive-semidefinite nullity with the strong Arnold property. Since the ordinary minimum rank $\operatorname{mr}(G)$ and the positive-semidefinite minimum rank $\operatorname{mr}_+(G)$ never exceed $\operatorname{mr}_\nu(G)$, this one inequality settles the weak graph complement conjecture for all three parameters with a universal constant below 2. The proof runs Mader's classical connectivity theorem through the known lower bound $\nu(G)\ge\lceil\kappa\rceil(G)$. The paper also makes partial progress on the $\delta$-conjecture, verifying $\nu(G)\ge\delta(G)$ for several girth and minimum-degree classes, and it determines the exact set of possible values of the degeneracy sum $l(G)+l(G^c)$.

What carries the argument

Two mechanisms carry the paper. The first is Mader's 1972 theorem: a graph of average degree at least $4(k-1)$ contains a $k$-connected subgraph; combined with $\nu(G)\ge\lceil\kappa\rceil(G)$, this converts edge density in $G$ or $G^c$ into a lower bound on $\nu$. The second is a degeneracy-pair analysis built on a greedy algorithm that constructs, for each admissible pair $(h,k)$, a graph with $l(G)=h$ and $l(G^c)=k$; the algorithm's correctness proof yields the exact Nordhaus-Gaddum range for $l(G)+l(G^c)$.

What would settle it

Any graph $G$ of order $n\ge4$ with $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) \ge (1+1/\sqrt2)n+1$ would disprove Theorem 2.3; a natural test family is the self-complementary Matula graphs of order $4s$ described in Remark 2.4, since the paper's own argument shows such graphs limit the connectivity-based method to $\tfrac32 n$.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2.3: for every graph $G$ of order $n\ge4$, $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) < (1+1/\sqrt2)n+1$. The proof first establishes, from Mader's theorem and the inequality $\nu(G)\ge\lceil\kappa\rceil(G)$, that $\nu(G) > (n-1)/2 - \sqrt{m(G^c)/2}$; applying this bound to both $G$ and $G^c$ and using $m(G)+m(G^c)=n(n-1)/2$ yields the constant $1+1/\sqrt2$. Because $\operatorname{mr}(G)\le\operatorname{mr}_+(G)\le\operatorname{mr}_\nu(G)$, the same inequality resolves the weak form of the graph complement conjecture for all key minimum-rank parameters. Alongside this, the paper shows $\nu(G) > \lceil d\rceil(G)/4$, proves the $\delta$-conjecture for constrained graph classes via girth and forbidden-subgraph hypotheses, and gives the sharp interval of possible degeneracy sums $l(G)+l(G^c)$.

Load-bearing premise

The load-bearing premise is the quoted theorem that $\nu(G)\ge\lceil\kappa\rceil(G)$: the maximum positive-semidefinite nullity with the strong Arnold property is never below the minor-monotone ceiling of vertex connectivity, and if that inequality failed, the universal constant $1+1/\sqrt2$ would not follow.

Editorial extensions

If this is right

The inequality $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) < (1+1/\sqrt2)n+1$ immediately gives the same weak-GCC bound for $\operatorname{mr}$ and $\operatorname{mr}_+$, since $\operatorname{mr}(G)\le\operatorname{mr}_+(G)\le\operatorname{mr}_\nu(G)$.
A by-product of the proof is a constant $b_\nu<2$ such that $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) \le b_\nu n$ for every graph, matching the original 'Question 2' form of the weak conjecture without the additive $+2$.
If the $\delta$-conjecture holds, the bound improves to $\operatorname{mr}_\nu(G)+\operatorname{mr}_\nu(G^c) \le \sqrt2\,n + 1$ (and, more elementarily, to $\tfrac32 n + \tfrac12$).
The $\delta$-conjecture for $\nu$ is verified for graphs with girth at least 11 and minimum degree at least 4, for girth 7–10 with minimum degree at least 193, for girth 5–6 with minimum degree at least $8\cdot10^6$, and for $K_{s,s'}$-free or $C_{2t}$-free graphs with sufficiently large minimum degree.
The degeneracy sum $l(G)+l(G^c)$ takes every integer value in the interval $[2n-1-\sqrt{2n^2-2n+1},\, n-1]$, and no values outside it; the endpoints are therefore best possible.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The unconditional constant $1+1/\sqrt2$ is probably not final: the Matula graphs in Remark 2.4 show the connectivity-subgraph method itself cannot beat $3/2$, so any improvement toward $3/2$ would need a genuinely different argument.
If the $\delta$-conjecture is eventually proved, the degeneracy theorem in Section 3 converts it immediately into the $\sqrt2\,n+1$ bound, so the exact degeneracy-sum range has a direct quantitative payoff.
The exact range of $l(G)+l(G^c)$ invites analogous exact Nordhaus-Gaddum characterizations for other minor-monotone parameters; the paper's Figure 1 already shows $\lceil\delta\rceil(G)+\lceil\delta\rceil(G^c)$ can exceed $n-1$, so this would require new arguments.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper settles the weak graph complement conjecture (the b < 2 version) for all the standard minimum rank parameters, with the explicit constant 1+1/sqrt(2) ≈ 1.707. That is a genuine open problem from the 2006 AIM workshop, and the proof is short and correct. It also gives a complete characterization of which sums l(G)+l(G^c) are realizable, which is a nice Nordhaus-Gaddum result in its own right.

What's new: the key idea is to apply Mader's theorem to force a highly connected subgraph in G and in G^c, then convert the connectivity to nu via the Lovász-Saks-Schrijver / van der Holst result (Theorem 1.6). I checked the root/floor calculation in Theorem 2.2 and the Cauchy step in Theorem 2.3; the algebra is clean. I don't find this Mader-based approach in the prior GCC literature. The degeneracy part is more involved: Algorithm 1 constructs graphs with prescribed degeneracy pair, and Theorem 3.7 shows that every integer in the interval [2n-1 - sqrt(2n^2-2n+1), n-1] is a possible sum. The induction in Theorem 3.4 is dense but I didn't find a gap.

Soft spots: the main theorem relies on Theorem 1.6, an external theorem, but it is standard and published, so that is not a real weakness. The delta conjecture section is partial in the honest sense: the results require large girth or large minimum degree, and the constants r(s,s') are existential rather than explicit. That is fine. The exposition could be tightened in Section 3; the proof of Fact 1 in Theorem 3.4 is hard to follow, but the claims are plausible and the structure is right. I have no mathematical objection.

This paper is for people working in combinatorial matrix theory or graph theory with matrix invariants. It deserves a serious referee; I would accept it for review without hesitation. The main theorem is important enough that referees should check the Mader application carefully, but it holds up.

Referee Report

0 major / 4 minor

Summary. The paper studies Nordhaus-Gaddum-type bounds for graph minimum rank parameters and the delta conjecture. Its main result, Theorem 2.3, proves that for every graph G of order n≥4, mr_ν(G)+mr_ν(G^c) < (1+1/sqrt(2))n+1, where mr_ν(G)=|G|-ν(G) and ν(G) is the maximum nullity among positive semidefinite matrices with the strong Arnold property. Since mr(G)≤mr_+(G)≤mr_ν(G), this gives an explicit constant below 2 and thereby resolves the Weak Graph Complement Conjecture (Conjecture 1.4) for all three key minimum rank parameters. The proof combines Mader's theorem on highly connected subgraphs with the known inequality ν(G)≥ceil(kappa)(G). The paper also proves partial results toward the delta conjecture for ν under girth and forbidden-subgraph conditions, characterizes the possible values of the degeneracy sum l(G)+l(G^c), and derives conditional improvements of the weak GCC assuming the delta conjecture.

Significance. The central result is significant: it settles a long-standing open weak form of the Graph Complement Conjecture with an explicit constant, using a short and transparent argument. The degeneracy characterization in Section 3 is a self-contained contribution of independent interest, and the partial delta-conjecture results are new and clearly presented. The paper does not use fitted parameters; all claimed constants are explicit where relevant, and conditional statements are carefully flagged. The main external input, ν(G)≥ceil(kappa)(G), is standard and is applied correctly. Overall the central claims are convincing and the proofs check out.

minor comments (4)

[§3, Algorithm 1] In Algorithm 1, line 1 reads 'maxlGc(n,h)', which is never defined and is not used by the algorithm; please remove it or replace it with an explicit initialization.
[§2, Theorem 2.2] The proof applies Mader's theorem with k=1 for graphs with fewer than n edges; please clarify the convention for 1-connectivity of a single vertex, or add a one-sentence trivial argument for the k=1 case so that the lower bound is unambiguous under either convention.
[§3, Theorem 3.7] The justification of the exceptional case in (19) is incorrect: the inequality floor(2n-1-sqrt(2n^2-2n+1)) < floor(2n-1-sqrt(2n^2-2n)) occurs when 2n^2-2n is a perfect square, not when 2n^2-2n+1 is a perfect square; the conclusion that the exceptional integer r is even remains correct, but the argument should be corrected.
[§3.1] Reference [28] is cited as 'Mitchel' in the text but appears as 'Mitchell' in the bibliography; please standardize the spelling.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main bound is derived from Mader's theorem and an external connectivity/nullity result, with no fitted input renamed as a prediction.

full rationale

The central claim, Theorem 2.3, is a direct derivation: it applies Mader's Theorem 2.1 to convert edge-count information into a k-connected subgraph, then uses the external Theorem 1.6 (nu(G) >= ceil(kappa)(G), due to Lovasz, Saks, Schrijver, and van der Holst) to pass from connectivity to a lower bound on nu. The inequalities in the proof are explicit algebraic manipulations, and the input quantities are only the order n and the sizes m(G) and m(G^c) of the graph and its complement. Nothing is fitted to the target inequality, and no equation in the proof is definitionally equivalent to the conclusion. The conditional results in Section 3 are explicitly labeled as assuming the delta conjecture, so they are not circular even though that conjecture is also the topic of partial resolution. Self-citations such as [4] and [5] are used for context or to state the conjectures, not as load-bearing evidence for Theorem 2.3. No uniqueness theorem or ansatz is imported from the current authors' prior work to force the main conclusion. Therefore the paper's claimed derivation chain is self-contained relative to standard external results, and no circular step is present.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

All non-trivial external results are standard published theorems; the only conjectural input is the delta-conjecture, used conditionally. No ad hoc constants or entities are introduced by the authors.

assumptions (7)

standard math Mader's theorem (Theorem 2.1): large average degree guarantees a k-connected subgraph.
Used in Theorems 2.2 and 2.5 to produce highly connected subgraphs, which then feed into nu(G) >= ceil(kappa)(G).
standard math nu(G) >= kappa(G) for every graph G (Theorem 1.6, derived from Lovasz-Saks-Schrijver and van der Holst).
The bridge from connectivity to the Colin de Verdiere-type parameter nu, the load-bearing step for the weak GCC resolution.
standard math Kuhn-Osthus theorems on minors in graphs of large girth (Theorem 2.7).
Used in Corollary 2.8 and Theorem 2.11 to get superlinear nu lower bounds for high-girth graphs.
standard math Krivelevich-Sudakov theorems on minors in graphs without complete bipartite subgraphs or even cycles (Theorem 2.9).
Used in Corollary 2.10 and Theorem 2.11(d,e).
standard math Mitchell's bound nu(G) >= |G| - 2l(G^c) - 1 (Theorem 3.9).
Used in Propositions 3.10 and 3.11 to link nu to complement degeneracy.
standard math Lick-White edge bound for k-degenerate graphs (Proposition 3.2).
Used to define covering pairs in the degeneracy sum characterization.
domain assumption The delta-conjecture (Conjecture 1.5: delta(G) <= l(G) <= ceil(delta)(G) <= nu(G)) is assumed true in Propositions 3.10 and 3.11.
The improved weak GCC constants 3/2 and sqrt(2) are conditional on this unproved conjecture; the paper explicitly labels the assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture." pith.science (2026). https://pith.science/paper/CD4NMMAR

@misc{pith2026250524577,
  author       = {Pith},
  title        = {Pith review of: The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CD4NMMAR}},
  note         = {Machine review of arXiv:2505.24577}
}

abstract

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 $\delta$-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 $\delta$-conjecture. Furthermore, we incorporate the assumption of the $\delta$-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\`ere number.

Figures

Figures reproduced from arXiv: 2505.24577 by the authors.

**Figure 2.** Complementary graphs of order 14 with l(G) = l(G c ) = 4 3.1 Weak graph complement conjecture improvements: variations In this subsection, we return to the Weak Graph Complement Conjecture and observe particular updates to the proposed bounds, upon assuming the validity of the δ-conjecture and referring to the results on graph degeneracy (see Theorem 3.7). We begin by noting that the role of degeneracy in relation t… view at source ↗

**Figure 3.** Known and suspected lower bounds on ν(G) Acknowledgments The authors’ collaboration began as part of the established “Inverse Eigenvalue Problems for Graphs and Zero Forcing” Research Community sponsored by the American Institute of Mathematics (AIM). We thank AIM for their support, and we thank the organizers and participants for contributing to this stimulating research experience. S.M. Fallat was supported in par… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

[1]

Achuthan, N

N. Achuthan, N. R. Achuthan, and L. Caccetta. On the Nordhaus-Gaddum class problems.Australasian Journal of Combinatorics, 2, 5–27, 1990

work page 1990
[2]

Barioli, W

AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioab ˘a, D. Cvetkovi´c, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pry- porova, I. Sciriha, W. So, D. Stevanovi´c, H. van der Holst, K. Vander Meulen, and A. Wangsness). Zero forcing sets and the minimum rank of graphs.Linear Algebra a...

work page 2008
[3]

Balogh and A

J. Balogh and A. V . Kostochka. Large minors in graphs with given independence number.Discrete Mathematics, 311(20), 2203–2215, 2011

work page 2011
[4]

Barioli, W

F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, and H. van der Holst. On the graph complement conjecture associated with minimum rank.Linear Algebra and Its Applications, 436, 4373–4391, 2012

work page 2012
[5]

Barioli, W

F. Barioli, W. Barrett, S. M. Fallat, T. H. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van Der Holst. Parameters related to tree-width, zero forcing, and maximum nullity of a graph.Journal of Graph Theory, 72(2), 146–177, 2013

work page 2013
[6]

Barioli, S.M

F. Barioli, S.M. Fallat, L. Hogben. A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs.Electronic Journal of Linear Algebra, 13, 387-404, 2005

work page 2005
[7]

Barrett, S

W. Barrett, S. M. Fallat, H. T. Hall, and L. Hogben. Note on Nordhaus-Gaddum problems for Colin de Verdi`ere type parameters.Electronic Journal of Combinatorics, 20(3), Paper 56, 9, 2013

work page 2013
[8]

Bernshteyn and A

A. Bernshteyn and A. Kostochka. On the number of edges in a graph with no (k+1)-connected sub- graphs.Discrete Mathematics, 339(2), 682–688, 2016

work page 2016

Show all 31 references

[9]

Chartrand and J

G. Chartrand and J. Mitchem. Graphical theorems of the Nordhaus-Gaddum class.Lecture Notes in Mathematics, 186, 55–61, 1971

1971
[10]

Colin de Verdi`ere

Y . Colin de Verdi`ere. On a new graph invariant and a criterion for planarity.Contemporary Mathemat- ics, 147, 137–147, 1993

1993
[11]

Diestel.Graph theory

R. Diestel.Graph theory. sixth edition, Graduate Texts in Mathematics, 173, Springer, Berlin, 2025

2025
[12]

Colin de Verdi`ere

Y . Colin de Verdi`ere. Multiplicities of eigenvalues and tree-width graphs.Journal of Combinatorial Theory Series B, 74(2), 121–146, 1998

1998
[13]

Fallat and L

S. Fallat and L. Hogben. The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra and Its Applications, 426, 558–582, 2007

2007
[14]

van der Holst

H. van der Holst. Three-connected graphs whose maximum nullity is at most three.Linear Algebra and Its Applications, 429, 625–632, 2007

2007
[15]

van der Holst, L

H. van der Holst, L. Lov ´asz, and A. Schrijver. The Colin de Verdi`ere graph parameter.Graph Theory and Computational Biology (Balatonlelle, 1996), 7, 29–85, 1999

1996
[16]

L. Hogben. Nordhaus-Gaddum problems for Colin deVerdi `ere type parameters, variants of tree-width, and related parameters.Recent Trends in Combinatorics, 159, 275–294, 2016

2016
[17]

Lin, and Bryan L

Leslie Hogben, Jephian C-H. Lin, and Bryan L. Shader.Inverse Problems and Zero Forcing for Graphs, volume 270. American Mathematical Society, 2022

2022
[18]

D. R. Lick and A. T. White.k-degenerate graphs.Canadian Journal of Mathematics, 22(5), 1082– 1096, 1970

1970
[19]

Lov ´asz, M

L. Lov ´asz, M. Saks, and A. Schrijver. Orthogonal representations and connectivity of graphs.Linear Algebra and its applications, 114, 439–454, 1989. 17

1989
[20]

A. V . Kostochka. Lower bound of the Hadwiger number of graphs by their average degree.Combina- torica, 4, 307–316, 1984

1984
[21]

Krivelevich and B

M. Krivelevich and B. Sudakov. Minors in expanding graphs.Geometric and Functional Analysis, 19(1), 294–331, 2009

2009
[22]

Kotlov, L

A. Kotlov, L. Lov ´asz, and S. Vempala. The Colin de Verd`ere number and sphere representations of a graph.Combinatorica, 17, 483–521, 1997

1997
[23]

K ¨uhn and D

D. K ¨uhn and D. Osthus. Minors in graphs of large girth.Random Structures&Algorithms, 22(2), 213–225, 2003

2003
[24]

W. Mader. Existenzn-fach zusammenh ¨angender Teilgraphen in Graphen gen ¨ugend grosser Kanten- dichte.Abhandlungen aus dem mathematischen Seminar der Universit¨ at Hamburg, 37, 86–97, 1972

1972
[25]

W. Mader. Homomorphies ¨atze f¨ur graphen.Mathematische Annalen, 178, 154–168, 1968

1968
[26]

W. Mader. Topological subgraphs in graphs of large girth.Combinatorica, 8(3), 405–412, 1998

1998
[27]

D. W. Matula. Ramsey theory for graph connectivity.Journal of Graph Theory, 7(1), 95–103, 1983

1983
[28]

Mitchell

L. Mitchell. Graph degeneracy and orthogonal vector representations.Electronic Journal of Linear Algebra, 39, 282–285, 2023

2023
[29]

S. K. Narayan and A. Sharawi. Bounds on the Sum of Minimum Semidefinite Rank of a Graph and its Complement.Electronic Journal of Linear Algebra, 34, 399-406, 2018

2018
[30]

T. H. Nguyen. Highly connected subgraphs with large chromatic number.SIAM Journal on Discrete Mathematics, 38(1), 243–260, 2024

2024
[31]

R. Yuster. A note on graphs withoutk-connected subgraphs.Ars Combinatoria, 67, 231–236, 2003. 18

2003

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Achuthan, N

N. Achuthan, N. R. Achuthan, and L. Caccetta. On the Nordhaus-Gaddum class problems.Australasian Journal of Combinatorics, 2, 5–27, 1990

work page 1990

[2] [2]

Barioli, W

AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioab ˘a, D. Cvetkovi´c, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pry- porova, I. Sciriha, W. So, D. Stevanovi´c, H. van der Holst, K. Vander Meulen, and A. Wangsness). Zero forcing sets and the minimum rank of graphs.Linear Algebra a...

work page 2008

[3] [3]

Balogh and A

J. Balogh and A. V . Kostochka. Large minors in graphs with given independence number.Discrete Mathematics, 311(20), 2203–2215, 2011

work page 2011

[4] [4]

Barioli, W

F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, and H. van der Holst. On the graph complement conjecture associated with minimum rank.Linear Algebra and Its Applications, 436, 4373–4391, 2012

work page 2012

[5] [5]

Barioli, W

F. Barioli, W. Barrett, S. M. Fallat, T. H. Hall, L. Hogben, B. Shader, P. van den Driessche, and H. van Der Holst. Parameters related to tree-width, zero forcing, and maximum nullity of a graph.Journal of Graph Theory, 72(2), 146–177, 2013

work page 2013

[6] [6]

Barioli, S.M

F. Barioli, S.M. Fallat, L. Hogben. A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs.Electronic Journal of Linear Algebra, 13, 387-404, 2005

work page 2005

[7] [7]

Barrett, S

W. Barrett, S. M. Fallat, H. T. Hall, and L. Hogben. Note on Nordhaus-Gaddum problems for Colin de Verdi`ere type parameters.Electronic Journal of Combinatorics, 20(3), Paper 56, 9, 2013

work page 2013

[8] [8]

Bernshteyn and A

A. Bernshteyn and A. Kostochka. On the number of edges in a graph with no (k+1)-connected sub- graphs.Discrete Mathematics, 339(2), 682–688, 2016

work page 2016