On generalized list $\G$-free colorings of graphs

Abstract

For given graph $H$ and graphical property $P$, the conditional chromatic number $\chi (H,P)$ of $H$, is the smallest number $k$, so that $V(H)$ can be decomposed into sets $V_1,V_2,\dots ,V_k$, in which $H[V_i]$ satisfies the property $P$, for each $1\le i\le k$. When property $P$ be that each color class contains no copy of $G$, we write ${\chi }_G(H)$ instead of $\chi (G,P)$, which is called the $G$-free chromatic number. Due to this, we say $H$ has a $k$-$G$-free coloring if there is a map $c:V(H)⟶\{1,\dots ,k\}$, so that each of the color classes of $c$ be $G$-free. Assume that for each vertex $v$ of a graph $H$ is assigned a set $L(V)$ of colors, called a color list. Set $g(L)=\{g(v):v\in V(H)\}$, that is the set of colors chosen for the vertices of $H$ under $g$. An $L$-coloring $g$ is called $G$-free, so that: \begin{itemize} \item $g(v)\in L(v)$, for any $v\in V(H)$. \item $H[V_i]$ is $G$-free for each $i=1,2,\dots ,L$. \end{itemize} If there exists an $L$-coloring of $H$, then $H$ is called $L$-$G$-free-colorable. A graph $H$ is said to be $k$-$G$-free-choosable if there exists an $L$-coloring for any list-assignment $L$ satisfying $|L(V)|\ge k$ for each $v\in V(H)$, and $H[V_i]$ be $G$-free for each $i=1,2,\dots ,L$. Let graph $H$ and a collection of graphs $\G$ are given, the $χ_{\G}^L(H)$ of $H$ is the last integer $k$, so that $H$ is $k$-$\G$-free-choosable i.e. $H[V_i]$ is $\G$-free for each $i=1,2,\dots ,k$ i.e. contains no copy of any member of $\G$. In this article, we show that ${\chi }_G^L(H)={\chi }_G(H)$ for some graph $H$ and $G$, ${\chi }_G^L(H\oplus H^{\prime })\le {\chi }_G^L(H)+{\chi }_G^L(H^{\prime })$ for each $G$, $H$, and $H^{\prime }$. Also, we show that $χ_{\G}(H\oplus K_n)=χ^L_{\G}(H\oplus K_n)$, where $\G$ is a collection of all $d$-regular graphs, and some $n$.