Triangles in a complete chromatic graph with three colors

Suppose that each edge of \(K_ N\) is assigned exactly one of three possible colors: blue, green, or red. After the coloring, let \(B\), \(G\) and \(R\) be the number of monochromatic blue, green and red triangles respectively, \(T\) the number of tricolored triangles and \(S_ 2\) the number of bicolored triangles. An old and difficult problem is to find \(\phi(N)\) the minimum value of \(B+G+R\) for any coloring of \(K_ N\) with blue, green, and red. Greenwood and Gleason proved that \(\phi(N)=0\) for \(2\leq N\leq 16\) and \(\phi(N)>0\) for \(N>16\). In this paper the author does not solve this problem, but he is able to give sharp bounds for certain combinations of the number of triangles of various kinds, for example: In any coloring of \(K_ N\) with three colors: \[ B+G+R+S_ 2/3\geq \begin{cases} N(N- 2)(N-3)/18, &\text{if } N\equiv 0,2\pmod3; \\ N(N-1)(N-4)/18, &\text{if }N\equiv 1\pmod3;\end{cases} \] \[ B+G+R\geq \begin{cases} T/2-N(N-2)/6, &\text{if }N\equiv 0,2\pmod3;\\ T/2- N(N-1)/6, &\text{if }N\equiv 1\pmod3.\end{cases} \] These results are extended for \(k\)- colorings of \(K_ N\).

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Triangles in a complete chromatic graph with three colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068844)