Conditional and Unique Coloring of Graphs

Abstract

For integers $k,r>0$, a conditional $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices of $G$ such that every vertex $v$ of degree $d(v)$ in $G$ is adjacent to at least $\min \{r,d(v)\}$ differently colored vertices. Given $r$, the smallest integer $k$ for which $G$ has a conditional $(k,r)$-coloring is called the $r$th order conditional chromatic number ${\chi }_r(G)$ of $G$. We give results (exact values or bounds for ${\chi }_r(G)$, depending on $r$) related to the conditional coloring of some graphs. We introduce \emph{unique conditional colorability} and give some related results. (Keywords. cartesian product of graphs; conditional chromatic number; gear graph; join of graphs.)

Under review in International Journal of Computer Mathematics

References in corpus (2)

• On conditional coloring of some graphs
• Conditional coloring of some parameterized graphs