INJECTIVELY DELTA CHOOSABLE GRAPHS
Seog‐Jin Kim, Won-Jin Park · Bulletin of the Korean Mathematical Society · 2013
An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbor receive distinct colors. A graph G is said to be injectively $k$ -choosable if any list $L(v)$ of size at least $k$ for every vertex $v$ allows an injective coloring ${\phi}(v)$ such that ${\phi}(v){\in}L(v)$ for every $v{\in}V(G)$ . The least $k$ for which G is injectively $k$ -choosable is the injective choosability number of G, denoted by ${\chi}^l_i(G)$ . In this paper, we obtain new sufficient conditions to be ${\chi}^l_i(G)={\Delta}(G)$ . Maximum average degree, mad(G), is defined by mad(G) = max{2e(H)/n(H) : H is a subgraph of G}. We prove that if mad(G) < $\frac{8k-3}{3k}$ , then ${\chi}^l_i(G)={\Delta}(G)$ where $k={\Delta}(G)$ and ${\Delta}(G){\geq}6$ . In addition, when ${\Delta}(G)=5$ we prove that ${\chi}^l_i(G)={\Delta}(G)$ if mad(G) < $\frac{17}{7}$ , and when ${\Delta}(G)=4$ we prove that ${\chi}^l_i(G)={\Delta}(G)$ if mad(G) < $\frac{7}{3}$ . These results generalize some of previous results in [1, 4].