×

Total coloring of planar graphs without adjacent chordal 6-cycles. (English) Zbl 1378.05075

Summary: A total coloring of a graph \(G\) is a coloring such that no two adjacent or incident elements receive the same color. In this field there is a famous conjecture, named total coloring conjecture, saying that the the total chromatic number of each graph \(G\) is at most \(\Delta+2\). Let \(G\) be a planar graph with maximum degree \(\Delta\geq 7\) and without adjacent chordal 6-cycles, that is, two cycles of length 6 with chord do not share common edges. In this paper, it is proved that the total chromatic number of \(G\) is \(\Delta+1\), which partly confirmed total coloring conjecture.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy JA, Murty USR (1976) Graph theory with applications. MacMillan, London · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[2] Behzad M (1965) Graphs and their chromatic numbers. Ph.D. Thesis, Michigan State University
[3] Borodin OV (1989) On the total coloring of planar graphs. J Reine Angew Math 394:180-185 · Zbl 0653.05029
[4] Borodin OV, Kostochka AV, Woodall DR (1997) Total colorings of planar graphs with large maximum degree. J Graph Theory 26:53-59 · Zbl 0883.05053 · doi:10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO;2-G
[5] Cai H, Wu JL, Sun L (2016) Total coloring of planar graphs without short cycles. J Comb Optim 31:1650-1664 · Zbl 1339.05068 · doi:10.1007/s10878-015-9859-9
[6] Chang GJ, Hou JF, Roussel N (2011) Local condition for planar graphs of maximum degree 7 to be 8-totally colorable. Discret Appl Math 159:760-768 · Zbl 1223.05037 · doi:10.1016/j.dam.2011.01.001
[7] Du DZ, Shen L, Wang YQ (2009) Planar graphs with maximum degree 8 and without adjacent triangles are \[99\]-total-colorable. Discret Appl Math 157:6035-6043 · Zbl 1209.05077 · doi:10.1016/j.dam.2009.02.011
[8] Hou JF, Liu B, Liu GZ, Wu JL (2011) Total colorings of planar graphs without 6-cycles. Discret Appl Math 159:157-163 · Zbl 1283.05101 · doi:10.1016/j.dam.2010.08.025
[9] Kostochka AV (1996) The total chromatic number of any multigraph with maximum degree five is at most seven. Discret Math 162:199-214 · Zbl 0871.05023 · doi:10.1016/0012-365X(95)00286-6
[10] Kowalik L, Sereni JS, S̆krekovski R (2008) Total-coloring of plane graphs with maximum degree nine. SIAM J Discret Math 22:1462-1479 · Zbl 1184.05046 · doi:10.1137/070688389
[11] Li H, Ding L, Liu B, Wang G (2015) Neighbor sum distinguishing total colorings of planar graphs. J Comb Optim 30:675-688 · Zbl 1325.05083 · doi:10.1007/s10878-013-9660-6
[12] 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 · Zbl 1204.05047 · doi:10.1016/j.disc.2009.05.006
[13] Qu C, Wang G, Wu J, Yu X (2016) On the neighbor sum distinguishing total coloring of planar graphs. Theor Comput Sci 609:162-170 · Zbl 1331.05084 · doi:10.1016/j.tcs.2015.09.017
[14] Qu C, Wang G, Yan G, Yu X (2015) Neighbor sum distinguishing total choosability of planar graphs. J Comb Optim. doi:10.1007/s10878-015-9911-9 · Zbl 1348.05082
[15] Sanders DP, Zhao Y (1999) On total 9-coloring planar graphs of maximum degree seven. J Graph Theory 31:67-73 · Zbl 0922.05025 · doi:10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C
[16] Shen L, Wang YQ (2009) Total colorings of planar graphs with maximum degree at least 8. Sci China Ser A 52(8):1733-1742 · Zbl 1190.05073 · doi:10.1007/s11425-008-0155-3
[17] Vizing VG (1968) Some unsolved problems in graph theory. Uspekhi Mat Nauk 23:117-134 (in Russian) · Zbl 0192.60502
[18] Wang B, Wu JL (2011) Total coloring of planar graphs with maximum degree seven and without intersecting 3-cycles. Discret Math 311:2025-2030 · Zbl 1244.05098 · doi:10.1016/j.disc.2011.05.038
[19] Wang B, Wu JL, Wang HJ (2014) Total coloring of planar graphs without chordal \[66\]-cycles. Discret Appl Math 171:116-121 · Zbl 1288.05104 · doi:10.1016/j.dam.2014.02.004
[20] Wang HJ, Liu B, Gu Y, Zhang X, Wu WL, Gao HW (2015) Total coloring of planar graphs without adjacent short cycles, J Comb Optim. doi:10.1007/s10878-015-9954-y · Zbl 1367.05081
[21] Wang HJ, Luo ZY, Liu B, Gu Y, Gao HW (2016) A note on the minimum total coloring of planar graphs. Acta Math Sin Engl Ser 32:967-974 · Zbl 1346.05086 · doi:10.1007/s10114-016-5427-1
[22] Wang HJ, Wu LD, Wu WL, Pardalos PM, Wu JL (2014) Minimum total coloring of planar graph. J Glob Optim 60:777-791 · Zbl 1308.90193 · doi:10.1007/s10898-013-0138-y
[23] Wang P, Wu JL (2004) A note on the total colorings of planar graphs without \[44\]-cycles. Discret Math 24:125-135 · Zbl 1056.05067
[24] Wang W (2007) Total chromatic number of planar graphs with maximum degree ten. J Graph Theory 54:91-102 · Zbl 1110.05037 · doi:10.1002/jgt.20195
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.