List injective coloring of planar graphs with girth

详细信息    查看全文

• 作者：Hong-Yu Chen^a ; ^{hongyuchen86@163.com" class="auth_mail" title="E-mail the corresponding author} ; Jian-Liang Wu^b
• 关键词：Planar graph ; List injective coloring ; Girth
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 December 2016
• 年：2016
• 卷：339
• 期：12
• 页码：3043-3051
• 全文大小：523 K

文摘

A vertex coloring of a graph G$G$ is called injective if any two vertices with a common neighbor receive distinct colors. A graph G$G$ is injectively k$k$-choosable if any list L$L$ of admissible colors on V(G)$V\left(G\right)$ of size k$k$ allows an injective coloring φ$\phi$ such that φ(v)∈L(v)$\phi \left(v\right)\in L\left(v\right)$ whenever v∈V(G)$v\in V\left(G\right)$. The least k$k$ for which G$G$ is injectively k$k$-choosable is denoted by ge" height="20" width="37" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16302060-si19.gif">${\chi }_i^l\left(G\right)$. In this paper, we show that if G$G$ is a planar graph with girth g&ge;6$g\&<font\; color="red">ge</font>;6$, then ge" height="20" width="102" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X16302060-si22.gif">${\chi }_i^l\left(G\right)\le \Delta +3$.