Bipartition-respecting packing coloring conjecture for hypercubes

From papers

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 n0n\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.

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

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

Solutions 0

No solutions have been posted yet.