MathDB

Regular graph with less monochrome edges

Source: 2021 China TST, Test 2, Day 1 P2

March 21, 2021

graph theoryGraph coloringcombinatorics

Problem Statement

Given positive integers

n,k

n \ge 2

. Find the minimum constant

c

satisfies the following assertion: For any positive integer

m

and a

kn

-regular graph

G

with

m

vertices, one could color the vertices of

G

with

n

different colors, such that the number of monochrome edges is at most

cm