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

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 1kn11\leq k\leq n-1, and suppose that n5n\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)(n1)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.

Sources & referencesView supporting material

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.