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

Total coloring of planar graphs without adjacent short cycles

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

Abstract

In the study of computer science, optimization, computation of Hessians matrix, graph coloring is an important tool. In this paper, we consider a classical coloring, total coloring. Let \(G=(V,E)\) be a graph. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements (vertex/edge) receive the same color. Let G be a planar graph with \(\varDelta \ge 8\). We proved that if for every vertex \(v\in V\), there exists two integers \(i_v,j_v\in \{3,4,5,6,7\}\) such that v is not incident with adjacent \(i_v\)-cycles and \(j_v\)-cycles, then the total chromatic number of graph G is \(\varDelta +1\).

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  • Bojarshinov VA (2001) Edge and total coloring of interal graphs. Discret Appl Math 114:23–28

    Article  MathSciNet  MATH  Google Scholar 

  • Bondy JA, Murty USR (1976) Graph theory with applications. MacMillan, London

    Book  MATH  Google Scholar 

  • Du DZ, Shen L, Wang YQ (2009) Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable. Discret Appl Math 157:2778–2784

    Article  MathSciNet  MATH  Google Scholar 

  • Kostochka AV (1996) The total chromatic number of any multigraph with maximum degree five is at most seven. Discret Math 162:199–214

    Article  MathSciNet  MATH  Google Scholar 

  • Kowalik L, Sereni J-S, S̆krekovski R (2008) Total-coloring of plane graphs with maximum degree nine. SIAM J Discret Math 22:1462–1479

    Article  MathSciNet  MATH  Google Scholar 

  • Liu B, Hou JF, Wu JL, Liu GZ (2009) Total colorings and list total colorings of planar graphs without intersecting 4-cycles. Discret Math 309:6035–6043

    Article  MathSciNet  MATH  Google Scholar 

  • McDiarmid CJH, Snchez-Arroyo A (1994) Total colorings regular bipartite graphs is NP-hard. Discret Math 124:155–162

    Article  MATH  Google Scholar 

  • Roussel N, Zhu X (2010) Total coloring of planar graphs of maximum degree eight. Inf Process Lett 110:321–324

    Article  MathSciNet  MATH  Google Scholar 

  • Sanchez-Arroyo A (1989) Determing the total colouring number is NP-hard. Discret Math 78:315–319

    Article  MathSciNet  MATH  Google Scholar 

  • Sanders DP, Zhao Y (1999) On total 9-coloring planar graphs of maximum degree seven. J Graph Theory 31:67–73

    Article  MathSciNet  MATH  Google Scholar 

  • Shen L, Wang YQ (2009) Total colorings of planar graphs with maximum degree at least 8. Sci China Ser A 52:1733–1742

    Article  MathSciNet  MATH  Google Scholar 

  • Tan X, Chen HY, Wu JL (2009) Total colorings of planar graphs without adjacent 4-cycles. In: The eighth international symposium on operations research and its applications (ISORA’09), 167–173

  • Wang GH, Yan GY, Yu JG, Zhang X (2013) The \(r\)-acyclic chromatic number of planar graphs. J Comb Optim. doi:10.1007/s10878-013-9680-2

  • Wang HJ, Wu LD, Wu WL (2014) Total coloring of planar graphs with maximum degree 8. Theor Comput Sci 522:54–61

    Article  MathSciNet  MATH  Google Scholar 

  • Wang HJ, Wu LD, Wu WL, Pardalos PM, Wu JL (2014) Minimum total coloring of planar graph. J Global Optim 60:777–791

    Article  MathSciNet  MATH  Google Scholar 

  • Wu JL (2004) Total coloring of series-parallel graphs. Ars Comb 73:215–217

    MathSciNet  MATH  Google Scholar 

  • Wu JL, Wang P (2008) List-edge and list-total colorings of graphs embedded on hyperbolic surfaces. Discret Math 308:6210–6215

    Article  MathSciNet  MATH  Google Scholar 

  • Yap HP (1996) Total colorings of graphs. Lecture notes in mathematics, vol 1623. Springer-Verlag, Berlin

Download references

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants 11301410, 11401386, 11402075, 11501316, 71171120, 71571108, the Projects of International (Regional) Cooperation and Exchanges of NSFC (71411130215), the Specialized Research Fund for the Doctoral Program of Higher Education (20133706110002), China Postdoctoral Science Foundation under Grants 2015M570568, 2015M570572, and the Shandong Provincial Natural Science Foundation of China under Grants ZR2014AQ001, ZR2015GZ007.

Author information

Authors and Affiliations

  1. College of Mathematics, Qingdao University, Qingdao, 266071, China

    Huijuan Wang, Yan Gu & Hongwei Gao

  2. Department of Mathematics, Ocean University of China, Qingdao, 266100, China

    Bin Liu

  3. School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China

    Xin Zhang

  4. College of Computer Science and Technology, TaiYuan University of Technology, Taiyuan, 030024, China

    Weili Wu

  5. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA

    Weili Wu

Authors
  1. Huijuan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yan Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xin Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Weili Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Hongwei Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bin Liu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, H., Liu, B., Gu, Y. et al. Total coloring of planar graphs without adjacent short cycles. J Comb Optim 33, 265–274 (2017). https://doi.org/10.1007/s10878-015-9954-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9954-y

Keywords

Search

Navigation