Skip to main content
Springer Nature Link
Log in

Neighbor sum distinguishing total colorings of triangle free planar graphs

  • Published:
Acta Mathematica Sinica, English Series Aims and scope Submit manuscript

Abstract

A total k-coloring c of a graph G is a proper total coloring c of G using colors of the set [k] = {1, 2, ..., k}. Let f(u) denote the sum of the color on a vertex u and colors on all the edges incident to u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv ∈ E(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 that χ″nsd(G) ≤ Δ(G)+3 for any simple graph with maximum degree Δ(G). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alon, N.: Combinatorial Nullstellensatz. Combin. Probab. Comput., 8, 7–29 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, North-Holland, New York, 1976

    MATH  Google Scholar 

  3. Chen, X.: On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3. Discrete Math., 308(17), 4003–4007 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  4. Ding, L., Wang, G., Yan, G.: Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz. Sci. China Ser. A, 57(9), 1875–1882 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ding, L., Wang, G., Wu, J., Yu, J.: Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, submitted

  6. Dong, A., Wang, G.: Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. Acta Math. Sin., Engl. Series, 30(4), 703–709 (2014)

    Article  MATH  MathSciNet  Google Scholar 

  7. Huang, D., Wang, W.: Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree (in Chinese). Sci. Sin. Math., 42(2), 151–164 (2012)

    Article  Google Scholar 

  8. Huang, P., Wong, T., Zhu, X.: Weighted-1-antimagic graphs of prime power order. Discrete Math., 312(14), 2162–2169 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  9. Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Combin. Theory Ser. B, 91(1), 151–157 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Li, H., Ding, L., Liu, B., et al.: Neighbor sum distinguishing total colorings of planar graphs. J. Comb. Optim., DOI: 10.1007/s10878-013-9660-6

  11. Li, H., Liu, B., Wang, G.: Neighor sum distinguishing total colorings of K 4-minor free graphs. Front. Math. China, 8(6), 1351–1366 (2013)

    Article  MathSciNet  Google Scholar 

  12. Pilśniak, M., Woźniak, M.: On the total-neighbor-distinguishing index by sums. Graph and Combin., DOI 10.1007/s00373-013-1399-4

  13. Przybyło, J.: Irregularity strength of regular graphs. Electron. J. Combin., 15(1), #R82, 10pp (2008)

    Google Scholar 

  14. Przybyło, J.: Linear bound on the irregularity strength and the total vertex irregularity strength of graphs. SIAM J. Discrete Math., 23(1), 511–516 (2009)

    Article  Google Scholar 

  15. Przybyło, J., Woźniak, M.: On a 1, 2 conjecture. Discrete Math. Theor. Comput. Sci., 12(1), 101–108 (2010)

    MATH  MathSciNet  Google Scholar 

  16. Przybyło, J., Woźniak, M.: Total weight choosability of graphs. Electron. J. Combin., 18, #P112, 11pp (2011)

  17. Seamone, B.: The 1-2-3 conjecture and related problems: a survey, arXiv:1211.5122

  18. Wang, W., Huang, D.: The adjacent vertex distinguishing total coloring of planar graphs. J. Comb. Optim., DOI 10.1007/s10878-012-9527-2

  19. Wang, W., Wang, P.: On adjacent-vertex-distinguishing total coloring of K 4-minor free graphs. Sci. China, Ser. A, 39(12), 1462–1472 (2009)

    Google Scholar 

  20. Kalkowski, M., Karoński, M., Pfender, F.: Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. J. Combin. Theory Ser. B, 100, 347–349 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  21. Wong, T., Zhu, X.: Total weight choosability of graphs. J. Graph Theory, 66, 198–212 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  22. Wong, T., Zhu, X.: Antimagic labelling of vertex weighted graphs. J. Graph Theory, 3(70), 348–359 (2012)

    Article  MathSciNet  Google Scholar 

  23. Zhang, Z., Chen, X., Li, J., et al.: On adjacent-vertex-distinguishing total coloring of graphs. Sci. China, Ser. A, 48(3), 289–299 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, University of Ji’nan, Ji’nan, 250022, P. R. China

    Ji Hui Wang, Qiao Ling Ma & Xue Han

Authors
  1. Ji Hui Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qiao Ling Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xue Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ji Hui Wang.

Additional information

Supported by National Natural Science Foundation of China (Grant No. 11201180) and the Scientific Research Foundation of University of Ji’nan (Grant No. XKY1120)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, J.H., Ma, Q.L. & Han, X. Neighbor sum distinguishing total colorings of triangle free planar graphs. Acta. Math. Sin.-English Ser. 31, 216–224 (2015). https://doi.org/10.1007/s10114-015-4114-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10114-015-4114-y

Keywords

MR(2010) Subject Classification

Search

Navigation