Refined separation-number conjecture for the complete graph K4

From papers

Let sep(K4,a,b)\mathsf{sep}(K_4,a,b) denote the separation threshold for the complete graph K4K_4.

K4 separation-number conjecture.

sep(K4,a,b)={2(ab)3,ba<2b,4a6b13,2ba<3b,2a4b,3ba<4b,\na,a4b.\mathsf{sep}(K_4,a,b)=\left\{\begin{array}{ll} \left\lfloor\frac{2(a-b)}{3}\right\rfloor, & b\leq a<2b,\\ \left\lceil\frac{4a-6b-1}{3}\right\rceil, & 2b\leq a<3b,\\ 2a-4b, & 3b\leq a<4b,\na, & a\geq4b. \end{array}\right.

The paper states that only the range 2ba<3b2b\leq a<3b remained to be verified. Thus the displayed piecewise formula is proposed as a refinement of the general separation-number conjecture, with the middle case identified as the unresolved part in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Jean-Christophe Godin, Rémi Grisot and Olivier Togni, “On List Coloring with Separation of the Complete Graph and Set System Intersections”, arXiv:2209.03436 (2022).

Solutions 0

No solutions have been posted yet.