Bull. Korean Math. Soc. 2013; 50(4): 1303-1314
Printed July 1, 2013
https://doi.org/10.4134/BKMS.2013.50.4.1303
Copyright © The Korean Mathematical Society.
Seog-Jin Kim and Won-Jin Park
Konkuk University, Seoul National University
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 {\em 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 {\em the injective choosability number } of $G$, denoted by $\chi_i^{l} (G)$. In this paper, we obtain new sufficient conditions to be $\chi_i^l (G) = \Delta(G)$. Maximum average degree, $\mbox{mad}(G)$, is defined by $\mbox{mad}(G) = \mbox{max} \{ {2e(H)}/{n(H)} : H \mbox{ is a subgraph of } G \}$. We prove that if $\mbox{mad}(G) < \frac{8k -3}{3k}$, then $\chi_i^l (G) = \Delta(G)$ where $k = \Delta(G)$ and $\Delta(G) \geq 6$. In addition, when $\Delta(G) = 5$ we prove that $\chi_i^l (G) = \Delta(G)$ if $\mbox{mad}(G) < \frac{17}{7}$, and when $\Delta(G) = 4$ we prove that $\chi_i^l (G) = \Delta(G)$ if $\mbox{mad}(G) < \frac{7}{3}$. These results generalize some of previous results in \cite{BI-2011, CKY}.
Keywords: injective coloring, list coloring, maximum average degree, discharging
MSC numbers: Primary 05C15
2014; 51(2): 511-517
2012; 49(2): 359-365
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd