Injectively $(\mathrm{\Delta }+1)$-Choosable Graphs

Abstract

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 $\varphi (v)$ such that $\varphi (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 }_i^l(G)$. In this paper, we obtain new sufficient conditions to ensure ${\chi }_i^l(G)\le \mathrm{\Delta }(G)+1$. We prove that if $mad(G)\le \frac{12k}{4k+3}$, then ${\chi }_i^l(G)=\mathrm{\Delta }(G)+1$ where $k=\mathrm{\Delta }(G)$ and $k\ge 4$. Typically, proofs using the discharging technique are different depending on maximum average degree $mad(G)$ or maximum degree $\mathrm{\Delta }(G)$. The main objective of this paper is finding a function $f(\mathrm{\Delta }(G))$ such that ${\chi }_i^l(G)\le \mathrm{\Delta }(G)+1$ if $mad(G)<f(\mathrm{\Delta }(G))$, which can be applied to every $\mathrm{\Delta }(G)$.