Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A total [k]-coloring of a graph G is a mapping \(\phi \): \(V(G)\cup E(G)\rightarrow [k]=\{1, 2,\ldots , k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. In a total [k]-coloring \(\phi \) of G, let \(C_{\phi }(v)\) denote the set of colors of the edges incident to v and the color of v. If for each edge uv, \(C_{\phi }(u)\ne C_{\phi }(v)\), we call such a total [k]-coloring an adjacent vertex distinguishing total coloring of G. \(\chi ''_{a}(G)\) denotes the smallest value k in such a coloring of G. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that if a planar graph G with maximum degree \(\Delta \ge 8\) contains no adjacent 4-cycles, then \(\chi ''_{a}(G)\le \Delta +3\).

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

  • Alon N (1999) Combinatorial nullstellensatz. Comb. Probab. Comput. 8:7–29

    Article  MathSciNet  MATH  Google Scholar 

  • Appel K, Haken W (1977) Every planar graph map is four colorable. Part I: discharging. Ill J Math 21:429–490

    MATH  Google Scholar 

  • Appel K, Haken W, Koch J (1977) Every planar graph map is four colorable. Part II: reducibility. Ill J Math 21:491–567

    MATH  Google Scholar 

  • Bondy J, Murty U (1976) Graph theory with applications. North-Holland, New York

    Book  MATH  Google Scholar 

  • Bartnicki T, Bosek B, Czerwiński S et al (2014) Additive coloring of planar graphs. Graphs Comb. 30:1087–1098

    Article  MathSciNet  MATH  Google Scholar 

  • Coker T, Johannson K (2012) The adjacent vertex distinguishing total chromatic number. Discret Math 312(17):2741–2750

    Article  MathSciNet  MATH  Google Scholar 

  • Cheng X, Wang G, Wu J (2016) The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta =10\). J Comb Optim. doi:10.1007/s10878-016-9995-x

  • Cheng X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta =3\). Discret Math 308(17):4003–4007

    Article  MathSciNet  Google Scholar 

  • Dong A, Wang G, Zhang J (2014) Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree. Discret Appl Math 166:84–90

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Huang D, Wang W, Yan C (2012) A note on the adjacent vertex distinguishing total chromatic number of graphs. Discret Math 312(24):3544–3546

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Przybyło J (2008) Irregularity strength of regular graphs. Electron J Comb 15(1):82

    MathSciNet  MATH  Google Scholar 

  • Przybyło J, Woźniak M (2011) Total weight choosability of graphs. Electron J Comb 18:112

    MathSciNet  MATH  Google Scholar 

  • Qu C, Wang G, Wu J, Yu X (2015) On the neighbor sum distinguishing total coloring of planar graphs. Theor Comput Sci. doi:10.1016/j.tcs.2015.09.017

  • Sanders D, Zhao Y (2001) Planar graphs of maximum degree seven are class I. J Comb Theory Ser B 83:201–212

    Article  MathSciNet  MATH  Google Scholar 

  • Seamone B (2012) The 1-2-3 conjecture and related problems: a survey. arXiv: 1211.5122

  • Wang W, Wang Y (2008) Adjacent vertex distinguishing total coloring of graphs with lower average degree. Taiwan J Math 12:979–990

    MathSciNet  MATH  Google Scholar 

  • Wang G, Yan G (2014) An improved upper bound for the neighbor sum distinguishing index of graphs. Discret Appl Math 175:126–128

    Article  MathSciNet  MATH  Google Scholar 

  • Wang G, Chen Z, Wang J (2014) Neighbor sum distinguishing index of planar graphs. Discret Math 334:70–73

    Article  MathSciNet  MATH  Google Scholar 

  • Wang H (2007) On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta (G)=3\). J Comb Optim 14:87–109

    Article  MathSciNet  MATH  Google Scholar 

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

    Google Scholar 

  • Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123–133

    Article  MathSciNet  MATH  Google Scholar 

  • Wang W, Huang D (2014) The adjacent vertex distinguishing total coloring of planar graphs. J Combin Optim 27(2):379–396

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang Z, Cheng X, Li J, Yao B, Lu X, Wang J (2005) On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A 48(3):289–299

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work is partially supported by NSFC (11271006).

Author information

Authors and Affiliations

  1. Department of Mathematics, Changji University, Changji, 831100, China

    Lin Sun

  2. School of Mathematics, Shandong University, Jinan, 250100, China

    Lin Sun, Xiaohan Cheng & Jianliang Wu

Authors
  1. Lin Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaohan Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jianliang Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jianliang Wu.

Appendix

Appendix

figure a

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, L., Cheng, X. & Wu, J. The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles. J Comb Optim 33, 779–790 (2017). https://doi.org/10.1007/s10878-016-0004-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-016-0004-1

Keywords

Mathematics Subject Classification

Search

Navigation