Maximum 3-separator conjecture for planar quadrangulations

Let n14n\geq 14. A 3-connected planar quadrangulation is a 3-connected planar graph in which every face is bounded by a cycle of length four. Let G\mathcal{G}^\ast be the class constructed by starting with a 4-cycle, successively adding vertices as described in the source construction, and gluing two disjoint copies of the cube Q3Q_3 along specified 4-cycles of the resulting quadrangulation. A 3-separator is non-trivial when it is a 3-separator in the sense used for these quadrangulations. Maximum 3-separator conjecture. The nn-vertex 3-connected planar quadrangulations with the maximum number of 3-separators are exactly the nn-vertex graphs in G\mathcal{G}^\ast. The construction gives graphs with exactly 4n144n-14 non-trivial 3-separators, within ten of the maximum possible value by the cited lemmas; determining whether these are the unique extremal graphs remains open.

Sources & referencesView supporting material

Primary source

J. Pascal Gollin, Kevin Hendrey, Abhishek Methuku, Casey Tompkins and Xin Zhang, “Counting cliques in 1-planar graphs”, arXiv:2109.02906 (2021).

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.