Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T19:52:07.223Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangles in a complete chromatic graph

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

A. W. Goodman
A. W. Goodman
Affiliation:
Department of MathematicsUniversity of South FloridaTampa, Florida 33620, U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Suppose that in a complete graph on N points, each edge is given arbitrarily either the color red or the color blue, but the total number of blue edges is fixed at T. We find the minimum number of monochromatic triangles in the graph as a function of N and T. The maximum number of monochromatic triangles presents a more difficult problem. Here we propose a reasonable conjecture supported by examples.

MSC classification

Secondary: 05C15: Coloring of graphs and hypergraphs
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 39 , Issue 1 , August 1985 , pp. 86 - 93
Copyright
Copyright © Australian Mathematical Society 1985

References

[1]Behzad, Mehdi and Chartrand, Gary, Introduction to the theory of graphs (Allyn and Bacon, Inc., Boston, 1971).Google Scholar
[2]Goodman, A. W., ‘On sets of acquaintances and strangers at any party’, Amer. Math. Monthly 66 (1959), 778–783.CrossRefGoogle Scholar
[3]Goodman, A. W., ‘Triangles in a complete chromatic graph with three colors’, Discrete Math. to appear.Google Scholar
[4]Sauvé, Leopold, ‘On chromatic graphs’, Amer. Math. Monthly 68 (1961), 107–111.CrossRefGoogle Scholar