Geodesic
Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 977-989.

Voir la notice de l'article provenant de la source Library of Science

A total-k-coloring of a graph G is a coloring of V ∪ E using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ′′(G) of G is the smallest integer k such that G has a total-k-coloring. Let G be a graph embedded in a surface of Euler characteristic ε ≥ 0. If G contains no 3-cycles adjacent to 4-cycles, that is, no 3-cycle has a common edge with a 4-cycle, then χ′′(G) ≤ max8, Δ+1.
Keywords: total coloring, embedded graph, cycle 
@article{DMGT_2018_38_4_a7,
     author = {Wang, Bing and Wu, Jian-Liang and Sun, Lin},
     title = {Total {Colorings} of {Embedded} {Graphs} with {No} {3-Cycles} {Adjacent} to {4-Cycles}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {977--989},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a7/}
}
TY  - JOUR
AU  - Wang, Bing
AU  - Wu, Jian-Liang
AU  - Sun, Lin
TI  - Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 977
EP  - 989
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a7/
LA  - en
ID  - DMGT_2018_38_4_a7
ER  - 
%0 Journal Article
%A Wang, Bing
%A Wu, Jian-Liang
%A Sun, Lin
%T Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 977-989
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a7/
%G en
%F DMGT_2018_38_4_a7
Wang, Bing; Wu, Jian-Liang; Sun, Lin. Total Colorings of Embedded Graphs with No 3-Cycles Adjacent to 4-Cycles. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 977-989. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a7/

[1] M. Behzad, Graphs and Their Chromatic Numbers (Ph.D. Thesis, Michigan State University, 1965).

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan Press Ltd., London, 1976).

[3] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180–185.

[4] O.V. Borodin, Coupled colourings of graphs on a plane, Metody Diskret. Anal. 45 (1987) 21–27, in Russian.

[5] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B 71 (1997) 184–204. doi:10.1006/jctb.1997.1780

[6] O.V. Borodin A.V. Kostochka and D.R. Woodall, Total colorings of planar graphs with large maximum degree, J. Graph Theory 26 (1997) 53–59. doi:10.1002/(SICI)1097-0118(199709)26:1h53::AID-JGT6i3.0.CO;2-G

[7] G.J. Chang, J. Hou and N. Roussel, Local condition for planar graphs of maximum degree 7 to be 8- totally colorable, Discrete Appl. Math. 159 (2011) 760–768. doi:10.1016/j.dam.2011.01.001

[8] D. Du, L. Shen and Y. Wang, Planar graphs with maximum degree 8 and without adjacent triangles are 9- totally-colorable, Discrete Appl. Math. 157 (2009) 2778–2784. doi:10.1016/j.dam.2009.02.011

[9] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley Interscience, 1995).

[10] Ł. Kowalik, J.-S. Sereni and R. Škrekovski, Total-colorings of plane graphs with maximum degree nine, SIAM J. Discrete Math. 22 (2008) 1462–1479. doi:10.1137/070688389

[11] L. Shen and Y.Q. Wang, Total colorings of planar graphs with maximum degree atleast 8, Sci. China Ser A: Math. 52 (2009) 1733–1742. doi:10.1007/s11425-008-0155-3

[12] L. Shen and Y. Wang, On the 7 total colorability of planar graphs with maximum degree 6 and without 4- cycles, Graphs Combin. 25 (2009) 401–407. doi:10.1007/s00373-009-0843-y

[13] A.V. Kostochka, The total coloring of a multigraph with maximal degree 4, Discrete Math. 17 (1977) 161–163. doi:10.1016/0012-365X(77)90146-7

[14] A.V. Kostochka, An analogue of Shannon’s estimate for complete colorings, Metody Diskret. Anal. 30 (1977) 13–22, in Russian.

[15] A.V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math. 162 (1996) 199–214. doi:10.1016/0012-365X(95)00286-6

[16] B. Liu, J.F. Hou, J.L. Wu and G.Z. Liu, Total colorings and list total colorings of planar graphs without intersecting 4- cycles, Discrete Math. 309 (2009) 6035–6043. doi:10.1016/j.disc.2009.05.006

[17] D.P. Sanders and Y. Zhao, On total 9- coloring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67–73. doi:10.1002/(SICI)1097-0118(199905)31:1h67::AID-JGT6i3.0.CO;2-C

[18] V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk 23 (1968) 117–134, in Russian.

[19] B. Wang and J.-L. Wu, Total coloring of planar graphs with maximum degree seven, Inform. Process. Lett. 111 (2011) 1019–1021. doi:10.1016/j.ipl.2011.07.012

[20] P. Wang and J.-L. Wu, A note on total colorings of planar graphs without 4- cycles, Discuss. Math. Graph Theory 24 (2004) 125–135. doi:10.7151/dmgt.1219

[21] H.J. Wang, L.D. Wu, W.L. Wu, P.M. Pardalos and J.L. Wu, Minimum total coloring of planar graph, J. Global Optim. 60 (2014) 777–791. doi:10.1007/s10898-013-0138-y

[22] H.J. Wang, B. Liu, J.L. Wu and G.Z. Liu, Total coloring of embedded graphs with maximum degree at least seven, Theoret. Comput. Sci. 518 (2014) 1–9. doi:10.1016/j.tcs.2013.04.030

[23] H.J. Wang, B. Liu, J.L. Wu and B. Wang, Total coloring of graphs embedded in surfaces of nonnegative Euler characteristic, Sci. China Math. 57 (2014) 211–220. doi:10.1007/s11425-013-4576-2

[24] J.L. Wu and P. Wang, List-edge and list-total colorings of graphs embedded on hyperbolic surfaces, Discrete Math. 308 (2008) 6210–6215. doi:10.1016/j.disc.2007.11.044

[25] W.F. Wang, Total chromatic number of planar graphs with maximum degree ten, J. Graph Theory 54 (2007) 91–102. doi:10.1002/jgt.20195