Maximum 3-separator conjecture for planar quadrangulations
Maximum 3-separator conjecture for planar quadrangulations
Let . A 3-connected planar quadrangulation is a 3-connected planar graph in which every face is bounded by a cycle of length four. Let 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 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 -vertex 3-connected planar quadrangulations with the maximum number of 3-separators are exactly the -vertex graphs in . The construction gives graphs with exactly 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.