Bounded nonrepetitive connection conjecture for 2-connected graphs
Let be a graph, and let denote the least number of colors in a nonrepetitive connected coloring of .
Bounded nonrepetitive connection conjecture. There exists a constant such that every -connected graph satisfies
The paper establishes finite bounds for several more highly connected classes, including -connected graphs, but leaves the existence of a uniform bound for all -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
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.