← All problems

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

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
  1. 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.