TOPICS

# Guy's Conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph is

 (1)

where is the floor function, which can be rewritten

 (2)

The values for , 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).

Guy (1972) proved the conjecture for , a result extended to by Pan and Richter (2007).

It is known that

 (3)

(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).

Complete Bipartite Graph, Complete Graph, Graph Crossing Number, Zarankiewicz's Conjecture

## Explore with Wolfram|Alpha

More things to try:

## References

Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of Is 62." 22 Sep 2000. http://arxiv.org/abs/cs/0009023.de Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular -Representation." Math Program. 109, 613-624, 2007.de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "Improved Bounds for the Crossing Numbers of and ." 2004. https://arxiv.org/pdf/math/0404142.pdf.Guy, R. K. "The Crossing Number of the Complete Graph." Bull. Malayan Math. Soc. 7, 68-72, 1960.Guy, R. K. "Crossing Numbers of Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.Pan, S. and Richter, R. B. "The Crossing Number of is 100." J. Graph Th. 56, 128-134, 2007.Sloane, N. J. A. Sequence A000241/M2772 in "The On-Line Encyclopedia of Integer Sequences."

Guy's Conjecture

## Cite this as:

Weisstein, Eric W. "Guy's Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GuysConjecture.html