Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front Math Chin    0, Vol. Issue () : 1351-1366    https://doi.org/10.1007/s11464-013-0322-x
RESEARCH ARTICLE
Neighbor sum distinguishing total colorings of K4-minor free graphs
Hualong LI, Bingqiang LIU, Guanghui WANG()
School of Mathematics, Shandong University, Jinan 250100, China
 Download: PDF(152 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

A total [k]-coloring of a graph G is a mapping ?: V (G) ∪E(G) → {1,2, ..., k} such that any two adjacent elements in V (G)∪E(G) receive different colors. Let f(v) denote the sum of the colors of a vertex v and the colors of all incident edges of v. A total [k]-neighbor sum distinguishing-coloring of G is a total [k]-coloring of G such that for each edge uvE(G),f(u)f(v). By χnsd(G), we denote the smallest value k in such a coloring of G. Pil?niak and Wo?niak conjectured χnsd(G)?(G)+3 for any simple graph with maximum degree Δ(G). This conjecture has been proved for complete graphs, cycles, bipartite graphs, and subcubic graphs. In this paper, we prove that it also holds for K4-minor free graphs. Furthermore, we show that if G is a K4-minor free graph with ?(G)4, then χnsd(G)?(G)+2 The bound Δ(G) + 2 is sharp.

Keywords K4-minor free graph      neighbor sum distinguishing (nsd)     
Corresponding Author(s): WANG Guanghui,Email:ghwang@sdu.edu.cn   
Issue Date: 01 December 2013
 Cite this article:   
Hualong LI,Bingqiang LIU,Guanghui WANG. Neighbor sum distinguishing total colorings of K4-minor free graphs[J]. Front Math Chin, 0, (): 1351-1366.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-013-0322-x
https://academic.hep.com.cn/fmc/EN/Y0/V/I/1351
1 Behzad M. Graphs and Their Chromatic Numbers. Doctoral Thesis . East Lansing: Michigan State University, 1965
2 Bondy J A, Murty U S R. Graph Theory with Applications. New York: North-Holland, 1976
3 Chen X. On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3. Discrete Math , 2008, 308: 4003-4007
doi: 10.1016/j.disc.2007.07.091
4 Dong A, Wang G. Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math Sin (Engl Ser) (to appear)
5 Kostochka A V. The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Math , 1996, 162: 199-214
doi: 10.1016/0012-365X(95)00286-6
6 Molloy M, Reed B. A bound on the total chromatic number. Combinatorics , 1998, 18: 241-280
doi: 10.1007/PL00009820
7 Pil?niak M, Wo?niak M. On the adjacent-vertex-distinguishing index by sums in total proper colorings. http://www.ii.uj.edu.pl/preMD/index.php
8 Rosenfeld M. On the total coloring of certain graphs. Israel J Math , 1971, 9: 396-402
doi: 10.1007/BF02771690
9 Vijayaditya N. On total chromatic number of a graph. J Lond Math Soc (2) , 1971, 3: 405-408
10 Vizing V G. Some unsolved problems in graph theory. Uspehi Mat Nauk , 1968, 23: 117-134
11 Wang H. On the adjacent vertex distinguishing total chromatic number of the graphs with Δ(G) = 3. J Comb Optim , 2007, 14: 87-109
doi: 10.1007/s10878-006-9038-0
12 Wang W, Wang P. On adjacent-vertex-distinguishing total coloring of K4-minor free graphs. Sci China Ser A , 2009, 39(12): 1462-1472
13 Wang W, Wang Y. Adjacent vertex distinguishing edge colorings of K4-minor free graph. Appl Math Lett , 2011, 24: 2034-2037
doi: 10.1016/j.aml.2011.05.038
14 Wang Y,Wang W. Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim , 2010, 19: 123-133
doi: 10.1007/s10878-008-9165-x
15 Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J. On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A , 2005, 48(3): 289-299
doi: 10.1360/03YS0207
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed