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