← All problems

The 3m conjecture for irregularising walks

1 year old · traced to

Let GG be a nice graph of size mm, and let MLW(G){\rm ML}^{\rm W}(G) denote the minimum size of an irregularising walk of GG. The 3m conjecture for irregularising walks states that

MLW(G)≤3m.{\rm ML}^{\rm W}(G) \leq 3m.

The paper proves the general upper bound MLW(G)≤4m{\rm ML}^{\rm W}(G)\leq 4m and gives examples with parameter about 2m2m; it conjectures that the factor 33 is sufficient for every nice graph, motivated by subdivided stars whose parameter is expected to approach 3m3m.

References
  1. Julien Bensmail, Romain Bourneuf, Paul Colinot, Samuel Humeau and Timothée Martinod, “Making Graphs Irregular through Irregularising Walks”, arXiv:2506.21254 (2025).

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.