Bounded nonrepetitive connection conjecture for 2-connected graphs

About 14 years old · traced to

Let GG be a graph, and let nrc⁡(G)\operatorname{nrc}(G) denote the least number of colors in a nonrepetitive connected coloring of GG.

Bounded nonrepetitive connection conjecture. There exists a constant tt such that every 22-connected graph GG satisfies

nrc⁡(G)≤t.\operatorname{nrc}(G)\leq t.

The paper establishes finite bounds for several more highly connected classes, including 44-connected graphs, but leaves the existence of a uniform bound for all 22-connected graphs open.

References

Primary source

Michał Dębski, Jarosław Grytczuk, Paweł Naroski and Małgorzata Śleszyńska-Nowak, “Strongly proper connected coloring of graphs”, arXiv:2301.10578 (2023).

Additional references

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

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.