Chartrand et al.'s odd-order maximum-size conjecture for rainbow disconnection number

At least 7 years old · documented by

Let GG be a connected graph of order nn, and let rd(G)rd(G) be its rainbow disconnection number, the minimum number of colors needed in an edge-coloring so that every pair of vertices is separated by a rainbow edge-cut. Let kk and nn be integers with 1≤k≤n−11\leq k\leq n-1, and suppose that n≥5n\geq 5 is odd.

Chartrand et al.'s conjecture. The maximum size of a connected graph GG of order nn with rd(G)=krd(G)=k is

(k+1)(n−1)2.\frac{(k+1)(n-1)}{2}.

This is the odd-order maximum-size question left by the earlier determination of the corresponding minimum size. The paper presents the result as a conjecture posed by Chartrand et al. and states elsewhere that it solves the conjecture.

References

Primary source

Xuqing Bai, Renying Chang and Xueliang Li, “More on rainbow disconnection in graphs”, arXiv:1810.09736 (2018).

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.