MathDB
Each edge is at most n cycles implies chromatic number bound

Source: Komal 2021 A807

November 22, 2021
combinatoricsgraph theoryspanning treekomal

Problem Statement

Let n>1n>1 be a given integer. Let GG be a finite simple graph with the property that each of its edges is contained in at most nn cycles. Prove that the chromatic number of the graph is at most n+1n+1.
Back to ProblemsView on AoPS