The Colin de Verdière graph complement conjecture

Let GG be a finite simple graph and let G\overline{G} denote its complement. Let μ(G)\mu(G) denote the Colin de Verdière parameter. Colin de Verdière's graph complement conjecture. Every graph GG satisfies

μ(G)+μ(G)V(G)2.\mu(G)+\mu(\overline{G})\geq |V(G)|-2.

This is the complement analogue of Nordhaus–Gaddum-type inequalities for graph parameters and is related in the paper to the extremal edge conjecture for the Colin de Verdière parameter. The source presents it as a conjecture; no resolution is supplied there.

Sources & referencesView supporting material

Primary source

Rose McCarty, “The Extremal Function and Colin de Verdière Graph Parameter”, arXiv:1706.07451 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.