Neighbor sum distinguishing total chromatic number of K₄-minor free graph

Abstract

A k-total coloring of a graph G is a mapping φ: V (G) ∪ E(G) →{1, 2, . . . , k} such that no two adjacent or incident elements in V (G) ∪ E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v. We say that φ is a k-neighbor sum distinguishing total coloring of G if f(u) ≠ f(v) for each edge uv ∈ E(G). Denote {{\displaystyle X}}_{\mathrm{\Sigma }}^{\text{'}\text{'}}(G) the smallest value k in such a coloring of G. Pilśniak andWoźniak conjectured that for any simple graph with maximum degree Δ(G), {{\displaystyle X}}_{\Sigma }^{\text{'}\text{'}}(G)\le \mathrm{\Delta }(G)+\mathrm{3}. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K₄-minor free graph G with Δ(G)≥5, {{\displaystyle X}}_{\mathrm{\Sigma }}^{\text{'}\text{'}}(G)=\mathrm{\Delta }(G)+\mathrm{1} if G contains no two adjacent Δ-vertices, otherwise, {{\displaystyle X}}_{\mathrm{\Sigma }}^{\text{'}\text{'}}(G)=\mathrm{\Delta }(G)+\mathrm{2}.

Keywords

Neighbor sum distinguishing total coloring / Combinatorial Nullstellensatz / K₄-minor free graph

References

[1] AlonN. Combinatorial Nullstellensatz.Combin Probab Comput, 1999, 8: 7–29

[2] BondyJ, MurtyU. Graph Theory with Applications.New York: North-Holland, 1976

[3] ChengX, HuangD, WangG, WuJ. Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ.Discrete Appl Math, 2015, 190-191: 34–41

[4] DingL, WangG, YanG. Neighbour sum distinguishing total colorings via the Combinatorial Nullstellensatz.Sci China Math, 2014, 57(9): 1875–1882

[5] DongA, WangG. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree.Acta Math Sin (Engl Ser), 2014, 30(4): 703–709

[6] LiH, DingL, LiuB, WangG. Neighbor sum distinguishing total colorings of planar graphs.J Comb Optim, 2015, 30(3): 675–688

[7] LiH, LiuB, WangG. Neighbor sum distinguishing total colorings of K4-minor free graphs.Front Math China, 2013, 8(6): 1351–1366

[8] PilśniakM, WoźniakM. On the adjacent-vertex-distinguishing index by sums in total proper colorings.

[9] PrzybyloJ. Neighbour sum distinguishing total colorings via the Combinatorial Nullstellensatz.Discrete Appl Math, 2016, 202: 163–173

[10] QuC, WangG, WuJ, YuX. On the neighbour sum distinguishing total coloring of planar graphs.Theoret Comput Sci, 2016, 609: 162–170

[11] QuC, WangG, YanG, YuX. Neighbor sum distinguishing total choosability of planar graphs.J Comb Optim, 2016, 32(3): 906–916

[12] WangJ, MaQ, HanX. Neighbor sum distinguishing total colorings of triangle free planar graphs.Acta Math Sin (Engl Ser), 2015, 31(2): 216–224

[13] WangJ, MaQ, HanX, WangX. A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles.J Comb Optim, 2016, 32(2): 626–638

[14] YaoJ, ShaoZ, XuC. Neighbor sum distinguishing total choosability of graphs with Δ = 3.Adv Math (China), 2016, 45(3): 343–348

[15] YaoJ, XuC. Neighbour sum distinguishing total coloring of graphs with maximum degree 3 or 4.J Shandong Univ Nat Sci, 2015, 50(2): 9–13

[16] YaoJ, YuX, WangG, XuC. Neighbour sum (set) distinguishing total choosability of d-degenerate graphs.Graphs Combin, 2016, 32: 1611–1620

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg