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

Total coloring of planar graphs without short cycles

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

Abstract

The total chromatic number of a graph \(G\), denoted by \(\chi ''(G)\), is the minimum number of colors needed to color the vertices and edges of \(G\) such that no two adjacent or incident elements get the same color. It is known that if a planar graph \(G\) has maximum degree \(\Delta (G)\ge 9\), then \(\chi ''(G)=\Delta (G)+1\). In this paper, it is proved that if \(G\) is a planar graph with \(\Delta (G)\ge 7\), and for each vertex \(v\), there is an integer \(k_v\in \{3,4,5,6,7,8\}\) such that there is no \(k_v\)-cycle which contains \(v\), then \(\chi ''(G)=\Delta (G)+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
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Behzad M (1965) Graphs and their chromatic numbers, Ph.D. Thesis, Michigan State University

  • Borodin OV (1989) On the total coloring of planar graphs. J Reine Angew Math 394:180–185

    MathSciNet  MATH  Google Scholar 

  • Borodin OV, Kostochka AV, Woodall DR (1997) Total colorings of planar graphs with large maximum degree. J Graph Theory 26:53–59

    Article  MathSciNet  MATH  Google Scholar 

  • Chang GJ, Hou JF, Roussel N (2011) Local condition for planar graphs of maximum degree 7 to be 8-totally colorable. Discrete Appl Math 159:760–768

    Article  MathSciNet  MATH  Google Scholar 

  • Chang J, Wang HJ, Wu JL, Y A (2013) Total coloring of planar graphs with maximum degree 8 and without 5-cycles with two chords. Theor Comput Sci 476:16–23

    Article  MATH  Google Scholar 

  • Du DZ, Shen L, Wang YQ (2009) Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable. Discrete 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. Discrete 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 Discrete 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. Discrete Math 309:6035–6043

    Article  MathSciNet  MATH  Google Scholar 

  • Leidner M (2014) A larger family of planar graphs that satisfy the total coloring conjecture. Graphs and Comb 30:377–388

    Article  MathSciNet  MATH  Google Scholar 

  • Roussel N (2011) Local condition for planar graphs of maximum degree 6 to be total 8-colorable. Taiwan J Math 15:87–99

    MathSciNet  MATH  Google Scholar 

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

    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) On the 7 total colorability of planar graphs with maximum degree 6 and without 4-cycles. Graphs Comb 25:401–407

    Article  MathSciNet  MATH  Google Scholar 

  • Shen L, Wang YQ (2010) planar graphs with maximum degree 7 and without 5-cycles are 8-totally-colorable. Discrete Math 310:2372–2379

    Article  MathSciNet  MATH  Google Scholar 

  • Vizing VG (1968) Some unsolved problems in graph theory. Uspekhi Mat Nauk 23:117–134 (in Russian)

    MathSciNet  MATH  Google Scholar 

  • Wang B, Wu JL (2012) Total colorings of planar graphs without intersecting 5-cycles. Discrete Appl Math 160:1815–1821

    Article  MathSciNet  MATH  Google Scholar 

  • Wang B, Wu JL, Wang HJ (2014) Total coloring of plansr graphs without chordal 6-cycles. Discrete Appl Math 171:116–121

    Article  MathSciNet  MATH  Google Scholar 

  • Wang HJ, Liu B, Wu JL (2014) Total coloring of planar graphs without chordal short cycles. Graphs Comb. doi:10.1007/s00373-014-1449-6

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Wang HJ, Wu JL (2012) A note on the total coloring of planar graphs without adjacent 4-cycles. Discrete Math 312:1923–1926

    Article  MathSciNet  MATH  Google Scholar 

  • Wang YQ, Sun Q, Tao X, Shen L (2011) Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable. Sci China A 41(1):95–104 (in chinese)

    Google Scholar 

Download references

Acknowledgments

This work is supported by NSFC (11271006) and the Scientific Research program of the Higher Education Institution of Xinjiang Uygur Autonomous Region (XJEDU2014S067) of China.

Author information

Authors and Affiliations

  1. School of Mathematics, Shandong University, Jinan, 250100, People’s Republic of China

    Hua Cai, Jianliang Wu & Lin Sun

  2. Department of Mathematics, Changji University, Changji, 831100, People’s Republic of China

    Hua Cai & Lin Sun

Authors
  1. Hua Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jianliang Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lin Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jianliang Wu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cai, H., Wu, J. & Sun, L. Total coloring of planar graphs without short cycles. J Comb Optim 31, 1650–1664 (2016). https://doi.org/10.1007/s10878-015-9859-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9859-9

Keywords

Search

Navigation