Locally Restricted Colorings of Graphs

Abstract

Let $G$ be a simple graph and $f$ a function from the vertices of $G$ to the set of positive integers. An $(f,n)$-coloring of $G$ is an assignment of $n$ colors to the vertices of $G$ such that each vertex $x$ is adjacent to less than $f(x)$ vertices with the same color as $x$. The minimum $n$ such that an $(f,n)$-coloring of $G$ exists is defined to be the $f$-chromatic number of $G$. In this paper, we address a study of this kind of locally restricted coloring.