Year: 2023
Author: Danjun Huang, Dan Bao
Journal of Mathematical Study, Vol. 56 (2023), Iss. 2 : pp. 206–218
Abstract
For a given simple graph $G = (V(G),E(G)),$ a proper total-$k$-coloring $c : V(G)∪E(G)→ \{1,2,...,k\}$ is neighbor sum distinguishing if $f(u) ≠ f(v)$ for each edge $uv ∈ E(G),$ where $f(v) = \sum_{wv∈E(G)} c(wv)+c(v).$ The smallest integer $k$ in such a coloring of $G$ is the neighbor sum distinguishing total chromatic number, denoted by $\chi^{''}_{\sum} (G).$ It has been conjectured that $\chi ^{''}_{\sum} (G) ≤ ∆(G)+3$ for any simple graph $G.$ Let $mad (G)=max\{ \frac{2|E(H)|}{ |V(H)|} :H⊆G\}$ be the maximum average degree of $G.$ In this paper, by using the famous Combinatorial Nullstellensatz, we prove $\chi^{''} _{\sum}(G) ≤ max\{9,∆(G)+2\}$ for any graph $G$ with $mad (G)<4.$ Furthermore, we characterize the neighbor sum distinguishing total chromatic number for every graph $G$ with $mad (G)<4$ and $∆(G)≥8.$
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jms.v56n2.23.06
Journal of Mathematical Study, Vol. 56 (2023), Iss. 2 : pp. 206–218
Published online: 2023-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 13
Keywords: Neighbor sum distinguishing total coloring combinatorial nullstellensatz maximum average degree.