Refined separation-number conjecture for the complete graph K4

At least 3 years old · documented by

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(a−b)3⌋,b≤a<2b,⌈4a−6b−13⌉,2b≤a<3b,2a−4b,3b≤a<4b,na,a≥4b.\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 2b≤a<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.

References

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).

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.