Triangles in a complete chromatic graph with three colors
type: Item
instance of: scholarly article
title: Triangles in a complete chromatic graph with three colors
zbMATH Open document ID: 0582.05037
DOI: 10.1016/0012-365X(85)90175-X
author: A. W. Goodman
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3931051
zbMATH Keywords: monochromatic triangles
zbMATH Keywords: 3-coloring
zbMATH Keywords: extremal coloring
zbMATH Keywords: tricolored triangles
zbMATH Keywords: bicolored triangles
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Sur les proportions respectives de triangles uni, bi ou tricolores dans un tricoloriage des aretes du n-emble
cites work: On Sets of Acquaintances and Strangers at any Party
cites work: Q3703916
cites work: Combinatorial Relations and Chromatic Graphs
cites work: On Chromatic Graphs
cites work: Q4186343
description: scientific article; zbMATH DE number 3931051