Complementary-dimension bounds conjecture

About 11 years old · traced to

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.

References

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.