Introduction to Graph Theory · Problem 6.12

Colorings — Darij Grinberg

Mathematics — Graph Theory · non-proper-colorings-generalized

Problem

Let

k \in \mathbb{N}

. Let

p_1, p_2, \ldots, p_k

k

nonnegative real numbers such that

p_1 + p_2 + \cdots + p_k \geq 1

. Let

G = (V, E)

be a simple graph. Prove that there exists a

k

-coloring

f

G

with the following property: For each vertex

v \in V

, at most

p_{f(v)} \deg v

neighbors of

v

have the same color as

v