Research PaperNo Access

Two results on $K$ $K$ - $(2, 1)$ $(2, 1)$ -total choosability of planar graphs

Yan Song

School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China

E-mail Address: songy159@163.com

Search for more papers by this author

and

Lei Sun

https://orcid.org/0000-0002-5050-7630

School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China

E-mail Address: sunlei@sdnu.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S1793830920500810Cited by:0 (Source: Crossref)

Abstract

The $(2, 1)$ $(2, 1)$ -total choice number of $G$ $G$ , denoted by $C_{(2, 1)}^{T} (G)$ $C_{(2, 1)}^{T} (G)$ , is the minimum $k$ $k$ such that $G$ $G$ is $k$ $k$ - $(2, 1)$ $(2, 1)$ -total choosable. It was proved in [Y. Yu, X. Zhang and G. Z. Liu, List (d,1)-total labeling of graphs embedded in surfaces, Oper. Res. Trans.15(3) (2011) 29–37.] that $C_{p, 1}^{T} (G) \leq Δ + 2 p$ $C_{p, 1}^{T} (G) \leq Δ + 2 p$ if $G$ $G$ is a graph embedded in surface with Euler characteristic $𝜀$ $𝜀$ and $Δ (G)$ $Δ (G)$ big enough. In this paper, we prove that: (i) if $G$ $G$ is a planar graph with $Δ (G) \geq 7$ $Δ (G) \geq 7$ and $3$ $3$ -cycle is not adjacent to $k$ $k$ -cycle, $k \in {3, 4}$ $k \in {3, 4}$ , then $C_{(2, 1)}^{T} (G) \leq Δ + 4$ $C_{(2, 1)}^{T} (G) \leq Δ + 4$ ; (ii) if $G$ $G$ is a planar graph with $Δ (G) \geq 8$ $Δ (G) \geq 8$ and $i$ $i$ -cycle is not adjacent to $j$ $j$ -cycle, where $i, j \in {3, 4, 5}$ $i, j \in {3, 4, 5}$ , then $C_{(2, 1)}^{T} (G) \leq Δ + 3$ $C_{(2, 1)}^{T} (G) \leq Δ + 3$ .

Keywords:

AMSC: 05C15, 05C78

References

1. J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance 2, J. Discrete Math. 5 (1992) 586–595. Google Scholar
2. F. Havet, $(d, 1)$ $(d, 1)$ -Total labelling of graphs, Workshop on Graphs and Algorithms, Dijon, France (2003), pp. 3–12. Google Scholar
3. F. Havet and M. L. Yu, $(d, 1)$ $(d, 1)$ -Total labelling of graphs, Technical Report 4650, INRIA (2002), pp. 2–14. Google Scholar
4. F. Havet and M. L. Yu, $(p, 1)$ $(p, 1)$ -Total labelling of graphs, J. Discrete Math. 307 (2007) 199–207. Google Scholar
5. A. Kcmnitz and M. Marangio, $[r, s, t]$ $[r, s, t]$ -colorings of graphs, J. Discrete Math. 307 (2007) 199–207. Crossref, Google Scholar
6. L. Sun and J. L. Wu, On $(p, 1)$ $(p, 1)$ -total labelling of planar graphs, J. Comb. Optim. 33 (2017) 317–325. Crossref, Google Scholar
7. M. A. Whittlesey, J. P. Georges and D. W. Mauro, On the $λ$ $λ$ -number of $Q_{n}$ $Q_{n}$ and related graphs, J. Discrete Math. 8 (1995) 499–506. Google Scholar
8. Y. Yu, $[r, s, t; f]$ $[r, s, t; f]$ -colorings and $(p, 1)$ $(p, 1)$ -total labelling of graphs, D. Shandong Univ. 1 (2012) 25–79. Google Scholar
9. Y. Yu, G. H. Wang, G. Z. Liu and J. B. Li, $(2, 1)$ $(2, 1)$ -total labelling of planar graphs with large maximum degree, J. Discrete Math. 20 (2017) 1625–1636. Google Scholar
10. H. Y. Zhu, L. Y. Miao, S. Chen, X. Z. Lv and W. Y. Song, The list $L (2, 1)$ $L (2, 1)$ -labeling of planar graphs, J. Discrete Math. 341 (2018) 2211–2219. Crossref, Google Scholar