Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

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.

Injectively Delta choosable graphs

Seog-Jin Kim and Won-Jin Park

Konkuk University, Seoul National University

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 {\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