A. 807

Part of KoMaL A Problems 2021/2022

Problems(1)

Each edge is at most n cycles implies chromatic number bound

Source: Komal 2021 A807

n>1

be a given integer. Let

G

be a finite simple graph with the property that each of its edges is contained in at most

n

cycles. Prove that the chromatic number of the graph is at most

n+1

combinatoricsgraph theoryspanning treekomal