Complementary-dimension bounds conjecture

Let GG be a graph, let G\overline G be its complement, and let ρ\rho ^\perp denote orthogonal representation dimension. The complementary-dimension bounds conjecture. The two dimensions satisfy

ρ(G)+ρ(G)V(G)2\rho ^\perp(G)+\rho ^\perp(\overline G)\ge |V(G)|-2

and

ρ(G)+ρ(G)V(G)+2.\rho ^\perp(G)+\rho ^\perp(\overline G)\le |V(G)|+2.

The source states that these bounds are known for cycles and their complements, but otherwise says that they have not been proved; it also notes that the second bound is false for the general-position parameter.

Sources & referencesView supporting material

Primary source

Alberto Solís-Encina and José Ramón Portillo, “Orthogonal Representation of Graphs”, arXiv:1504.03662 (2015).

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.