patternMinor
Graph coloring variation
Viewed 0 times
coloringgraphvariation
Problem
Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?
Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,
$$| \{ w \in N_G(v) \mid \text{color}(v) = \text{color}(w) \} | \leq p?$$
Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,
$$| \{ w \in N_G(v) \mid \text{color}(v) = \text{color}(w) \} | \leq p?$$
Solution
The definition you are looking for is "defective coloring":
A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi _{d}(G)$.
A $(k, d)$-coloring of a graph G is a coloring of its vertices with k colours such that each vertex v has at most d neighbours having the same colour as the vertex v. We consider k to be a positive integer (it is inconsequential to consider the case when k = 0) and d to be a non-negative integer. Hence, $(k, 0)$-coloring is equivalent to proper vertex coloring.
The minimum number of colours k required for which G is $(k, d)$-colourable is called the $d$-defective chromatic number, $\chi _{d}(G)$.
Context
StackExchange Computer Science Q#127943, answer score: 7
Revisions (0)
No revisions yet.