Given a simple graph G = (V, E) and its (proper) total coloring ϕ with elements of the set {1, 2, ⋯, k}, let wϕ(v) denote the sum of the color of v and the colors of all edges incident with v. If for each edge uv ∈ E, wϕ(u) ≠ wϕ(v), we call ϕ a neighbor sum distinguishing total coloring of G. Let L = {Lx ∣ x ∈ V ⋃ E} be a set of lists of real numbers, each of size k. The neighbor sum distinguishing total choosability of G is the smallest k for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from Lx for each x ∈ V ⋃ E, and we denote it by <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1148_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ch}_{\sum}^{\prime\prime}(G)$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mtext>ch</mtext> <mrow> <mo>∑</mo> </mrow> <mrow> <mi mathvariant="normal">′</mi> <mi mathvariant="normal">′</mi> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation>. The known results of neighbor sum distinguishing total choosability are mainly about planar graphs. In this paper, we focus on 1-planar graphs. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. We prove that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1148_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="120" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ch}_{\sum}^{\prime\prime}(G)\leq\Delta+4$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msubsup> <mtext>ch</mtext> <mrow> <mo>∑</mo> </mrow> <mrow> <mi mathvariant="normal">′</mi> <mi mathvariant="normal">′</mi> </mrow> </msubsup> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>4</mn> </math></EquationSource> </InlineEquation> for any 1-planar graph G with Δ ≥ 15, where Δ is the maximum degree of G.

Neighbor Sum Distinguishing Total Choosability of 1-planar Graphs with Maximum Degree at Least 15

期刊论文
发表日期：

2025年6月24日

查看全文

Lin Sun,
De-rong Sun,
Xin Li,
Guang-long Yu

摘要

Given a simple graph G = (V, E) and its (proper) total coloring ϕ with elements of the set {1, 2, ⋯, k}, let w_ϕ(v) denote the sum of the color of v and the colors of all edges incident with v. If for each edge uv ∈ E, w_ϕ(u) ≠ w_ϕ(v), we call ϕ a neighbor sum distinguishing total coloring of G. Let L = {L_x ∣ x ∈ V ⋃ E} be a set of lists of real numbers, each of size k. The neighbor sum distinguishing total choosability of G is the smallest k for which for any specified collection of such lists, there exists a neighbor sum distinguishing total coloring using colors from L_x for each x ∈ V ⋃ E, and we denote it by $\text{ch}_{\sum}^{\prime\prime}(G)$ ${ch}_{\sum}^{''} (G)$ . The known results of neighbor sum distinguishing total choosability are mainly about planar graphs. In this paper, we focus on 1-planar graphs. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. We prove that $\text{ch}_{\sum}^{\prime\prime}(G)\leq\Delta+4$ ${ch}_{\sum}^{''} (G) \leq Δ + 4$ for any 1-planar graph G with Δ ≥ 15, where Δ is the maximum degree of G.