The cycle extension distinguishing number conjecture

Let CnC_n be the cycle graph on nn vertices, and let extD(Cn)\operatorname{ext}_D(C_n) denote the minimum number of blanks such that every coloring of the remaining vertices extends to a distinguishing coloring of CnC_n.

Cycle extension conjecture.

extD(Cn)={4if n≢0(mod4 or 5),5if n0(mod4),6if n0(mod5).\operatorname{ext}_D(C_n)=\begin{cases}4&\text{if }n\not\equiv 0\pmod{4\text{ or }5},\\5&\text{if }n\equiv 0\pmod 4,\\6&\text{if }n\equiv 0\pmod 5. \end{cases}

The conjecture is sharp for the displayed cases, and the paper verifies it whenever the minimum prime divisor of nn is at least 77; the general case remains open.

Sources & referencesView supporting material

Primary source

Michael Ferrara, Ellen Gethner, Stephen G. Hartke, Derrick Stolee and Paul S. Wenger, “Extending Precolorings to Distinguish Group Actions”, arXiv:1405.5558 (2014).

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.