Neighbor Sum Distinguishing Total Choosability of Cubic Graphs
- PDF / 441,078 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 214 Views
Neighbor Sum Distinguishing Total Choosability of Cubic Graphs Donghan Zhang1,2 · You Lu1,3 · Shenggui Zhang1,3 Received: 17 July 2019 / Revised: 2 December 2019 © Springer Japan KK, part of Springer Nature 2020
Abstract Let G = (V , E) be a graph and R be the set of real numbers. For a k-list total assignment L of G that assigns to each member z ∈ V ∪ E a set L z of k real numbers, a neighbor sum distinguishing (NSD) total L-coloring of G is a mapping φ : V ∪ E → R such that every member z ∈ V ∪ E receives a color of L z , every pair of adjacent or incident members in V ∪ E receive different colors, and z∈E G (u)∪{u} φ(z) = φ(z) for each edge uv ∈ E, where E (v) is the set of edges incident G z∈E G (v)∪{v} with v in G. In 2015, Pil´sniak and Wo´zniak posed the conjecture that every graph G with maximum degree has an NSD total L-coloring with L z = {1, 2, . . . , + 3} for any z ∈ V ∪ E, and confirmed the conjecture for all cubic graphs. In this paper, we extend their result by proving that every cubic graph has an NSD total L-coloring for any 6-list total assignment L.
You Lu’s work was partially supported by the National Natural Science Foundation of China (NO. 11871397) and the Natural Science Basic Research Plan in Shaanxi Province of China (NO. 2020JM-083). Shenggui Zhang’s work was partially supported by the National Natural Science Foundation of China (NO. 11671320 and U1803263) and the Fundamental Research Funds for the Central Universities (NO. 3102019ghjd003).
B
You Lu [email protected] Donghan Zhang [email protected] Shenggui Zhang [email protected]
1
School of Mathematics and Statistics, Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China
2
College of Mathematics and Computer Applications, Shangluo University, Shangluo 726000, Shaanxi, China
3
Xi’an-Budapest Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an 710072, Shaanxi, China
123
Graphs and Combinatorics
Keywords Cubic graphs · Neighbor sum distinguishing total choosability · Combinatorial Nullstellensatz
1 Introduction Every graph considered is finite and simple in this paper. For undefined terminology and notations here, we follow [2]. Let G be a graph with vertex set V (G) and edge set E(G). For a vertex u ∈ V (G), we use E G (u) to denote the set of edges incident with u. Let = (G) denote the maximum degree of G. We say that G is cubic if G is 3-regular, and is 2-degenerate if its any subgraph has at least one vertex with degree at most 2. Let k > 0 be an integer and T (G) = V (G) ∪ E(G). A mapping φ : T (G) → {1, 2, . . . , k} is called a proper k-total coloring of Gif φ(z 1 ) = φ(z 2 ) for any two adjacent or incident members z 1 , z 2 in T (G). We use z∈E G (u)∪{u} φ(z) to denote the sum of the colors of all members in E G (u) ∪ {u}. A proper k-total coloring φ of G is neighbor sum distinguishing (for short, NSD) if for each edge uv ∈ E(G), z∈E G (u)∪{u}
φ(z) =
φ(z).
z∈E G (v)∪{v}
The NSD total chromatic number of G, denoted by χt (G), is the
Data Loading...
