Let $ f: V(G)\cup E(G)\rightarrow \{1, 2, \dots, k\} $ be a total $ k $ -coloring of $ G $. Define a weight function on total coloring as
$ \phi(x) = f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y), $
where $ N(x) = \{y\in V(G)|xy\in E(G)\} $. If $ \phi(x)\neq \phi(y) $ for any edge $ xy\in E(G) $, then $ f $ is called a neighbor full sum distinguishing total $ k $ -coloring of $ G $. The smallest value $ k $ for which $ G $ has such a coloring is called the neighbor full sum distinguishing total chromatic number of $ G $ and denoted by fgndi $ _{\sum}(G) $. Suppose that $ H = T\cup C $ is a Halin graph, where $ T $ and $ C $ are called the characteristic tree and the adjoint cycle, respectively. Let $ V_0\subseteq V(H)\setminus V(C) $ and each vertex in $ V_0 $ is adjacent to some vertices on $ C $. In this paper, we prove that the neighbor full sum distinguishing total chromatic number of two types of Halin graphs are not more than three: (i) 3-regular Halin graphs and (ii) every vertex of $ V_0 $ of a Halin graph with degree at least 4. The above results support a conjecture that fgndi $ _{\sum}(G)\leq 3 $ for any connected graph $ G $ of order at least three (Chang et al., 2022).
Citation: Yinwan Cheng, Chao Yang, Bing Yao, Yaqin Luo. Neighbor full sum distinguishing total coloring of Halin graphs[J]. AIMS Mathematics, 2022, 7(4): 6959-6970. doi: 10.3934/math.2022386
Let $ f: V(G)\cup E(G)\rightarrow \{1, 2, \dots, k\} $ be a total $ k $ -coloring of $ G $. Define a weight function on total coloring as
$ \phi(x) = f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y), $
where $ N(x) = \{y\in V(G)|xy\in E(G)\} $. If $ \phi(x)\neq \phi(y) $ for any edge $ xy\in E(G) $, then $ f $ is called a neighbor full sum distinguishing total $ k $ -coloring of $ G $. The smallest value $ k $ for which $ G $ has such a coloring is called the neighbor full sum distinguishing total chromatic number of $ G $ and denoted by fgndi $ _{\sum}(G) $. Suppose that $ H = T\cup C $ is a Halin graph, where $ T $ and $ C $ are called the characteristic tree and the adjoint cycle, respectively. Let $ V_0\subseteq V(H)\setminus V(C) $ and each vertex in $ V_0 $ is adjacent to some vertices on $ C $. In this paper, we prove that the neighbor full sum distinguishing total chromatic number of two types of Halin graphs are not more than three: (i) 3-regular Halin graphs and (ii) every vertex of $ V_0 $ of a Halin graph with degree at least 4. The above results support a conjecture that fgndi $ _{\sum}(G)\leq 3 $ for any connected graph $ G $ of order at least three (Chang et al., 2022).
[1] | L. Addario-Berry, K. Dalal, C. McDiarmid, B. A. Reed, A. Thomason, Vertex-colouring edge-weightings, Combinatorica, 27 (2007), 1–12. https://doi.org/10.1007/s00493-007-0041-6 doi: 10.1007/s00493-007-0041-6 |
[2] | L. Addario-Berry, K. Dalal, B. A. Reed, Degree constrained subgraphs, Discrete Appl. Math., 156 (2008), 1168–1174. https://doi.org/10.1016/j.dam.2007.05.059 doi: 10.1016/j.dam.2007.05.059 |
[3] | J. A. Bondy, U. S. R. Murty, Graph theory, Springer, 2008. |
[4] | G. J. Chang, C. H. Lu, J. J. Wu, Q. L. Yu, Vertex-coloring edge-weightings of graphs, Taiwan. J. Math., 15 (2011), 1807–1813. https://doi.org/10.11650/twjm/1500406380 doi: 10.11650/twjm/1500406380 |
[5] | J. Z. Chang, C. Yang, Z. X. Yin, B. Yao, An extension on neighbor sum distinguishing total coloring of graphs, arXiv Preprint, 2022. Available from: https://arXiv.org/abs/2201.02781. |
[6] | E. Flandrin, H. Li, A. Marczyk, J. F. Saclé, M. Woźniak, A note on neighbor expanded sum distinguishing index, Discuss. Math. Graph T., 37 (2017), 29–37. https://doi.org/10.7151/dmgt.1909 doi: 10.7151/dmgt.1909 |
[7] | M. Kalkowski, A note on 1, 2-conjecture, Ph.D. Thesis, Poznan: Adam Mickiewicz University, 2009. |
[8] | M. Kalkowski, M. Karoński, F. Pfender, Vertex-coloring edge weightings: Towards the 1-2-3-conjecture, J. Combin. Theory B, 100 (2010), 347–349. https://doi.org/10.1016/j.jctb.2009.06.002 doi: 10.1016/j.jctb.2009.06.002 |
[9] | M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory B, 91 (2004), 151–157. https://doi.org/10.1016/j.jctb.2003.12.001 doi: 10.1016/j.jctb.2003.12.001 |
[10] | K. W. Lih, D. D. F. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett., 25 (2012), 898–901. https://doi.org/10.1016/j.aml.2011.10.046 doi: 10.1016/j.aml.2011.10.046 |
[11] | J. Przybylo, M. Woźniak, On a 1, 2 conjecture, Discrete Math. Theor. Comput. Sci., 12 (2010), 101–108. https://doi.org/10.46298/dmtcs.491 doi: 10.46298/dmtcs.491 |
[12] | J. Przybylo, The 1-2-3 conjecture almost holds for regular graphs, J. Combin. Theory B, 147 (2021), 183–200. https://doi.org/10.1016/j.jctb.2020.03.005 doi: 10.1016/j.jctb.2020.03.005 |
[13] | W. C. Shiu, P. C. B. Lam, W. K. Tam, On strong chromatic index of Halin graph, J. Combin. Math. Combin. Comput., 57 (2006), 211–222. |
[14] | J. Skowronek-Kaziów, 1, 2 conjecture-the multiplicative version, Inform. Process. Lett., 107 (2008), 93–95. https://doi.org/10.1016/j.ipl.2008.01.006 doi: 10.1016/j.ipl.2008.01.006 |
[15] | J. Skowronek-Kaziów, Multiplicative vertex-colouring weightings of graphs, Inform. Process. Lett., 112 (2012), 191–194. https://doi.org/10.1016/j.ipl.2011.11.009 doi: 10.1016/j.ipl.2011.11.009 |
[16] | T. Wang, Q. L. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China, 3 (2008), 581–587. https://doi.org/10.1007/s11464-008-0041-x doi: 10.1007/s11464-008-0041-x |
[17] | E. Q. Zhu, C. J. Liu, J. G. Yu, Neighbor product distinguishing total colorings of 2-degenerate graphs, J. Comb. Optim., 39 (2020), 72–76. https://doi.org/10.1007/s10878-019-00455-5 doi: 10.1007/s10878-019-00455-5 |
[18] | E. Q. Zhu, F. Jiang, C. J. Liu, J. Xu, Partition independent set and reduction-based approach for partition coloring problem, IEEE T. Cybernetics, 2020, 1–10. https://doi.org/10.1109/TCYB.2020.3025819 doi: 10.1109/TCYB.2020.3025819 |