List injective coloring of planar graphs with girth at least five
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A vertex coloring of a graph $G$ is called injective if any two vertices with a common neighbor receive distinct colors. A graph $G$ is injectively $k$-choosable if any list $L$ of admissible colors on $V(G)$ of size $k$ allows an injective coloring $\varphi$ such that $\varphi(v)\in L(v)$ whenever $v\in V(G)$. The least $k$ for which $G$ is injectively $k$-choosable is denoted by $\chi_{i}^{l}(G)$. For a planar graph $G$, Bu et al.~proved that $\chi_{i}^{l}(G)\leq\Delta+6$ if girth $g\geq5$ and maximum degree $\Delta(G)\geq8$. In this paper, we improve this result by showing that $\chi_{i}^{l}(G)\leq\Delta+6$ for $g\geq5$ and arbitrary $\Delta(G)$.
Abstract
A vertex coloring of a graph $G$ is called injective if any two vertices with a common neighbor receive distinct colors. A graph $G$ is injectively $k$-choosable if any list $L$ of admissible colors on $V(G)$ of size $k$ allows an injective coloring $\varphi$ such that $\varphi(v)\in L(v)$ whenever $v\in V(G)$. The least $k$ for which $G$ is injectively $k$-choosable is denoted by $\chi_{i}^{l}(G)$. For a planar graph $G$, Bu et al.~proved that $\chi_{i}^{l}(G)\leq\Delta+6$ if girth $g\geq5$ and maximum degree $\Delta(G)\geq8$. In this paper, we improve this result by showing that $\chi_{i}^{l}(G)\leq\Delta+6$ for $g\geq5$ and arbitrary $\Delta(G)$.
참고문헌 (19)
- O. V. Borodin, "List injective colorings of planar graphs", Discrete Math, 311(2-3), pp.154~165 (2011)[DOI]
- Y. H. Bu, "Injective coloring of planar graphs", Discrete Appl. Math, 157(4), pp.663~672 (2009)[DOI]
- Y. H. Bu, "List injective coloring of a class of planar graphs without short cycles", Discrete Math. Algorithms Appl, 10(5), pp.1850068~ (2018)[DOI]
- Y. H. Bu, "Injective coloring of planar graphs with girth 7", Discrete Math. Algorithms Appl, 4(2), pp.1250034~ (2012)[DOI]
- Y. H. Bu, "List injective coloring of planar graphs with girth 5, 6, 8", Discrete Appl. Math, 161(10-11), pp.1367~1377 (2013)[DOI]
- Y. H. Bu, "List injective coloring of planar graphs", Ars Combin, 141, pp.191~211 (2018)
- Y. H. Bu, "List injective coloring of planar graphs with girth g ≥ 5", Discrete Math. Algorithms Appl, 6(1), pp.1450006~ (2014)[DOI]
- H. Y. Chen, "List injective coloring of planar graphs with girth g ≥ 6", Discrete Math, 339(12), pp.3043~3051 (2016)[DOI]
- D. W. Cranston, "Injective colorings of sparse graphs", Discrete Math, 310(21), pp.2965~2973 (2010)[DOI]
- D. W. Cranston, "Injective colorings of graphs with low average degree", Algorithmica, 60(3), pp.553~568 (2011)[DOI]
- D. Dimitrov, "Injective coloring of planar graphs with Δ+2colors", ~
- W. Dong, "Injective coloring of planar graphs with girth 6", Discrete Math, 313(12), pp.1302~1311 (2013)[DOI]
- W. Dong, "Injective coloring of plane graphs with girth 5", Discrete Math, 315, pp.120~127 (2014)[DOI]
- A. Doyon, "Some bounds on the injective chromatic number of graphs", Discrete Math, 310(3), pp.585~590 (2010)[DOI]
- G. Hahn, "On the injective chromatic number of graphs", Discrete Math, 256(1-2), pp.179~192 (2002)[DOI]
- R. Li, "Injective choosability of planar graphs of girth five and six", Discrete Math, 312(6), pp.1260~1265 (2012)[DOI]
- B. Luzar, "Planar graphs with largest injective chromatic numbers", IMFM, 48, pp.1110~ (2010)
- B. Luzar, "Injective colorings of planar graphs with few colors", Discrete Math, 309(18), pp.5636~5649 (2009)[DOI]
- Graphs with Given Diameter and a Coloring Problem, "G. Wegner", University of Dortmund, ~ (1977)