Please wait a minute...

Frontiers of Mathematics in China

Front. Math. China    2017, Vol. 12 Issue (4) : 937-947     DOI: 10.1007/s11464-017-0649-9
RESEARCH ARTICLE |
Neighbor sum distinguishing total chromatic number of K4-minor free graph
Hongjie SONG, Changqing XU()
School of Science, Hebei University of Technology, Tianjin 300401, China
Download: PDF(165 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 uvE(G). Denote XΣ''(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), XΣ''(G)Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K4-minor free graph G with Δ(G)≥5, XΣ''(G)=Δ(G)+1 if G contains no two adjacent Δ-vertices, otherwise, XΣ''(G)=Δ(G)+2.

Keywords Neighbor sum distinguishing total coloring      Combinatorial Nullstellensatz      K4-minor free graph     
Corresponding Authors: Changqing XU   
Issue Date: 06 July 2017
 Cite this article:   
Hongjie SONG,Changqing XU. Neighbor sum distinguishing total chromatic number of K4-minor free graph[J]. Front. Math. China, 2017, 12(4): 937-947.
 URL:  
http://journal.hep.com.cn/fmc/EN/10.1007/s11464-017-0649-9
http://journal.hep.com.cn/fmc/EN/Y2017/V12/I4/937
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
Hongjie SONG
Changqing XU
1 AlonN. Combinatorial Nullstellensatz.Combin Probab Comput, 1999, 8: 7–29
doi: 10.1017/S0963548398003411
2 BondyJ, MurtyU. Graph Theory with Applications.New York: North-Holland, 1976
doi: 10.1007/978-1-349-03521-2
3 ChengX, HuangD, WangG, WuJ. Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ.Discrete Appl Math, 2015, 190-191: 34–41
doi: 10.1016/j.dam.2015.03.013
4 DingL, WangG, YanG. Neighbour sum distinguishing total colorings via the Combinatorial Nullstellensatz.Sci China Math, 2014, 57(9): 1875–1882
doi: 10.1007/s11425-014-4796-0
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
doi: 10.1007/s10114-014-2454-7
6 LiH, DingL, LiuB, WangG. Neighbor sum distinguishing total colorings of planar graphs.J Comb Optim, 2015, 30(3): 675–688
doi: 10.1007/s10878-013-9660-6
7 LiH, LiuB, WangG. Neighbor sum distinguishing total colorings of K4-minor free graphs.Front Math China, 2013, 8(6): 1351–1366
doi: 10.1007/s11464-013-0322-x
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
doi: 10.1016/j.dam.2015.08.028
10 QuC, WangG, WuJ, YuX. On the neighbour sum distinguishing total coloring of planar graphs.Theoret Comput Sci, 2016, 609: 162–170
doi: 10.1016/j.tcs.2015.09.017
11 QuC, WangG, YanG, YuX. Neighbor sum distinguishing total choosability of planar graphs.J Comb Optim, 2016, 32(3): 906–916
doi: 10.1007/s10878-015-9911-9
12 WangJ, MaQ, HanX. Neighbor sum distinguishing total colorings of triangle free planar graphs.Acta Math Sin (Engl Ser), 2015, 31(2): 216–224
doi: 10.1007/s10114-015-4114-y
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
doi: 10.1007/s10878-015-9886-6
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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed