The extremal characterization of complete bidirected graphs without rainbow triangles

Let DD be an arc-colored digraph of order n5n\geq 5, meaning that the arcs of DD are colored. A rainbow triangle is a directed triangle whose three arcs have pairwise distinct colors; write a(D)a(D) for the number of arcs and c(D)c(D) for the number of colors used by DD. Let Kn\overleftrightarrow{K}_{n} denote the complete bidirected graph on nn vertices.

Extremal characterization conjecture. If DD contains no rainbow triangles and

a(D)+c(D)=n(n1)+n24+1,a(D)+c(D)=n(n-1)+\left\lfloor\frac{n^{2}}{4}\right\rfloor+1,

then

DKn.D\cong\overleftrightarrow{K}_{n}.

The paper proves the corresponding assertion for n=3n=3 and n=4n=4; the conjecture proposes that the same conclusion holds for every n5n\geq 5.

Sources & referencesView supporting material

Primary source

Wei Li, Shenggui Zhang and Ruonan Li, “Rainbow triangles in arc-colored digraphs”, arXiv:1810.05960 (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.