Bipartition-respecting packing coloring conjecture for hypercubes
Bipartition-respecting packing coloring conjecture for hypercubes
Let be the -dimensional hypercube. A packing coloring respects bipartition if all vertices assigned color lie in one part of the bipartition. Let denote the packing chromatic number of , and let denote the minimum number of colors in a packing coloring of that respects its bipartition.
Bipartition-respecting packing coloring conjecture. For every ,
The invariant is an upper bound for the packing chromatic number, and the conjecture asserts that requiring color to be contained in one bipartition class does not increase the minimum number of colors. The exact value of 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
Sign in to submit a solution.
No solutions have been posted yet.