Let G =（V, E） be a graph and Ф ： V tA E → {1, 2,..., k） be a total-k-coloring of G. Let f（v）（S（v）） denote the sum（set） of the color of vertex v and the colors of the edges incident with v. The total colo...Let G =（V, E） be a graph and Ф ： V tA E → {1, 2,..., k） be a total-k-coloring of G. Let f（v）（S（v）） denote the sum（set） of the color of vertex v and the colors of the edges incident with v. The total coloring Ф is called neighbor sum distinguishing if （f（u） ≠ f（v）） for each edge uv∈ E（G）. We say that Фis neighbor set distinguishing or adjacent vertex distinguishing if S（u） ≠ S（v） for each edge uv ∈ E（G）. For both problems, we have conjectures that such colorings exist for any graph G if k 〉 △（G） ＋ 3. The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs, which is denoted by mad （G）. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that these two conjectures hold for sparse graphs in their list versions. More precisely, we prove that every graph G with maximum degree A（G） and maximum average degree mad（G） has ch＇＇∑（G） 〈 △（G） ＋ 3 （where ch＇＇∑（G） is the neighbor sum distinguishing total choice number of G） if there exists a pair （k, m） ∈ {（6, 4）, （5, 18/5）, （4, 16）} such that △（G） 〉 k and mad （G） 〈 m.展开更多
基金the National Natural Science Foundation of China(11371355,11471193)Foundation for Distinguished Young Scholars of Shandong Province(JQ201501)+2 种基金the Natural Science Foundation of Shandong Province(ZR2013AM001)the Fundamental Research Funds of Shandong UniversityIndependent Innovation Foundation of Shandong University(IFYT14012)
文摘Let G =（V, E） be a graph and Ф ： V tA E → {1, 2,..., k） be a total-k-coloring of G. Let f（v）（S（v）） denote the sum（set） of the color of vertex v and the colors of the edges incident with v. The total coloring Ф is called neighbor sum distinguishing if （f（u） ≠ f（v）） for each edge uv∈ E（G）. We say that Фis neighbor set distinguishing or adjacent vertex distinguishing if S（u） ≠ S（v） for each edge uv ∈ E（G）. For both problems, we have conjectures that such colorings exist for any graph G if k 〉 △（G） ＋ 3. The maximum average degree of G is the maximum of the average degree of its non-empty subgraphs, which is denoted by mad （G）. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that these two conjectures hold for sparse graphs in their list versions. More precisely, we prove that every graph G with maximum degree A（G） and maximum average degree mad（G） has ch＇＇∑（G） 〈 △（G） ＋ 3 （where ch＇＇∑（G） is the neighbor sum distinguishing total choice number of G） if there exists a pair （k, m） ∈ {（6, 4）, （5, 18/5）, （4, 16）} such that △（G） 〉 k and mad （G） 〈 m.
