The extremal characterization of complete bidirected graphs without rainbow triangles

At least 7 years old · documented by

Let DD be an arc-colored digraph of order n≥5n\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 K↔n\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(n−1)+⌊n24⌋+1,a(D)+c(D)=n(n-1)+\left\lfloor\frac{n^{2}}{4}\right\rfloor+1,

then

D≅K↔n.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 n≥5n\geq 5.

References

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.