Bipartition-respecting packing coloring conjecture for hypercubes

About 3 years old · traced to

Let QnQ_n be the nn-dimensional hypercube. A packing coloring respects bipartition if all vertices assigned color 11 lie in one part of the bipartition. Let χρ(Qn)\chi_\rho(Q_n) denote the packing chromatic number of QnQ_n, and let χρB(Qn)\chi_\rho^B(Q_n) denote the minimum number of colors in a packing coloring of QnQ_n that respects its bipartition.

Bipartition-respecting packing coloring conjecture. For every n≥0n\geq 0,

χρ(Qn)=χρB(Qn).\chi_\rho(Q_n)=\chi_\rho^B(Q_n).

The invariant χρB(Qn)\chi_\rho^B(Q_n) is an upper bound for the packing chromatic number, and the conjecture asserts that requiring color 11 to be contained in one bipartition class does not increase the minimum number of colors. The exact value of χρ(Q9)\chi_\rho(Q_9) is still undetermined, so the conjecture concerns the relationship between these two parameters rather than a currently known exact value.

References

Primary source

Petr Gregor, Jaka Kranjc, Borut Lužar and Kenny Štorgel, “Packing coloring of hypercubes with extended Hamming codes”, arXiv:2312.14576 (2023).

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.