Premium
On a Ramsey‐type problem
Author(s) -
Chung F. R. K.
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070110
Subject(s) - monochromatic color , combinatorics , mathematics , vertex (graph theory) , ramsey theory , graph , ramsey's theorem , type (biology) , complete graph , property (philosophy) , discrete mathematics , optics , physics , philosophy , epistemology , ecology , biology
Suppose a graph G has the property that if one colors the edges of G in r colors, there always exists a monochromatic triangle. Is it true that if one colors the edges of G in r + 1 colors so that every vertex is incident to at most r colors then there must be a monochromatic triangle? This problem, which was first raised by P. Erdös, is answered in the negative here.