Induced-matching avoidance conjecture for partial edge colorings of hypercubes

About 9 years old · traced to

Let QdQ_d be the dd-dimensional hypercube, and let φ\varphi be a partial dd-edge coloring of QdQ_d. A color class is the set of edges receiving one fixed color, and an induced matching is a matching whose endpoints induce no additional edges of QdQ_d. A partial coloring is avoidable if some proper dd-edge coloring of QdQ_d assigns a different color to every precolored edge than the one prescribed by φ\varphi. Induced-matching avoidance conjecture. If d\ba3d\ba3 and every color class of φ\varphi is an induced matching, then φ\varphi is avoidable. The paper proves this when dd is a multiple of 33, while conjecturing the statement for every d\ba1d\ba1; the supplied candidate is the stronger formulation with d\ba3d\ba3.

References

Primary source

Carl Johan Casselgren, Per Johansson and Klas Markström, “Avoiding and extending partial edge colorings of hypercubes”, arXiv:2104.00716 (2021).

Additional references

2 papers in this index state this conjecture (2017–2021). The statement above is taken from the most recent of them; the others are arXiv:1711.01066.

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.