Let $H$ be a fixed undirected graph. A vertex coloring of an undirected input graph $G$ is said to be an $H$-Free Coloring if none of the color classes contain $H$ as an induced subgraph. The $H$-Free Chromatic Number of $G$ is the minimum number of …
In an undirected graph, a proper $(k,i)$-coloring is an assignment of a set of $k$ colors to each vertex such that any two adjacent vertices have at most $i$ common colors. The $(k,i)$-coloring problem is to compute the minimum number of colors …
Given an undirected graph $G=(V,E)$ with $|V|=n$ and a vertex coloring, a vertex $v$ is happy if $v$ and all its neighbors have the same color. An edge is happy if its end vertices have the same color. Given a partial coloring of the vertices of the …
For a proper vertex coloring $c$ of a graph $G$, let $\varphi_c(G)$ denote the maximum, over all induced subgraphs $H$ of $G$, the difference between the chromatic number $\chi(H)$ and the number of colors used by $c$ to color $H$. We define the …