MathDB
n-colored graph without triangles

Source: China TST 1993, problem 3

June 27, 2005
graph theorycombinatorics unsolvedcombinatorics

Problem Statement

A graph G=(V,E)G=(V,E) is given. If at least nn colors are required to paints its vertices so that between any two same colored vertices no edge is connected, then call this graph ''n−n-colored''. Prove that for any n∈Nn \in \mathbb{N}, there is a n−n-colored graph without triangles.
Back to ProblemsView on AoPS