Geodesic
On the Entire Coloring Conjecture
Canadian mathematical bulletin, Tome 43 (2000) no. 1, pp. 108-114

Voir la notice de l'article provenant de la source Cambridge University Press

The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing’s Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta \,+\,1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta \,+\,4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \,\ge \,6$ .
DOI : 10.4153/CMB-2000-017-7
Mots-clés : 05C15, 05C10 
Sanders, Daniel P.; Zhao, Yue. On the Entire Coloring Conjecture. Canadian mathematical bulletin, Tome 43 (2000) no. 1, pp. 108-114. doi: 10.4153/CMB-2000-017-7
@article{10_4153_CMB_2000_017_7,
     author = {Sanders, Daniel P. and Zhao, Yue},
     title = {On the {Entire} {Coloring} {Conjecture}},
     journal = {Canadian mathematical bulletin},
     pages = {108--114},
     year = {2000},
     volume = {43},
     number = {1},
     doi = {10.4153/CMB-2000-017-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2000-017-7/}
}
TY  - JOUR
AU  - Sanders, Daniel P.
AU  - Zhao, Yue
TI  - On the Entire Coloring Conjecture
JO  - Canadian mathematical bulletin
PY  - 2000
SP  - 108
EP  - 114
VL  - 43
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2000-017-7/
DO  - 10.4153/CMB-2000-017-7
ID  - 10_4153_CMB_2000_017_7
ER  - 
%0 Journal Article
%A Sanders, Daniel P.
%A Zhao, Yue
%T On the Entire Coloring Conjecture
%J Canadian mathematical bulletin
%D 2000
%P 108-114
%V 43
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2000-017-7/
%R 10.4153/CMB-2000-017-7
%F 10_4153_CMB_2000_017_7

[1] [1] Appel, K. and Haken, W., Every planar map is four colorable. Bull. Amer. Math. Soc. 82 (1976), 711–712. Google Scholar

[2] [2] Borodin, O. V., Solution of Ringel's problem on vertex-face coloring of plane graphs and coloring of 1-planar graphs (Russian). Metody Diskret. Analiz. 41 (1984), 12–26. Google Scholar

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

[4] [4] Borodin, O. V., Structural theorem on plane graphs with application to the entire coloring number. J. Graph Theory 23 (1996), 233–239. Google Scholar

[5] [5] Fiamčík, J., Simultaneous colouring of 4-valent maps. Mat. Čas. 21 (1971), 9–13. Google Scholar

[6] [6] Jensen, T. R. and B. Toft, Graph Coloring Problems. John Wiley & Sons, Inc., New York, 1995, 47–48, 86–89, 193–194. Google Scholar

[7] [7] Jucovič, E., On a problem in map colouring. Mat. Čas. 19 (1969), 225–227. Google Scholar

[8] [8] Kronk, H. V. and Mitchem, J., The entire chromatic number of a normal graph is at most seven. Bull. Amer. Math. Soc. 78 (1972), 799–800. Google Scholar

[9] [9] Kronk, H. V. and Mitchem, J., A seven-color theorem on the sphere. Discrete Math. 5 (1973), 253–260. Google Scholar

[10] [10] Melnikov, L. S., Problem 9. Recent Advances in Graph Theory (ed. M. Fiedler), Academia Praha, Prague, 1975, 543. Google Scholar

[11] [11] Molloy, M. and Reed, B., A bound on the total chromatic number. Combinatorica 18 (1998), 241–280. Google Scholar

[12] [12] Ringel, G., Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29 (1965), 107–117. Google Scholar

[13] [13] Robertson, N., Sanders, D. P., Seymour, P. D. and Thomas, R., The four-colour theorem. J. Combin. Theory Ser. B 70 (1997), 2–44. Google Scholar

[14] [14] Sanders, D. P. and Zhao, Y., On simultaneous edge-face colorings of plane graphs. Combinatorica 17 (1997), 441–445. Google Scholar

[15] [15] Sanders, D. P. and Zhao, Y., On total 9-coloring planar graphs of maximum degree seven. J. Graph Theory 31 (1999), 67–73. Google Scholar

[16] [16] Sanders, D. P. and Zhao, Y., Planar graphs of maximum degree seven are Class I. Submitted. Google Scholar

[17] [17] Vizing, V. G., On an estimate of the chromatic index of a p-graph (Russian).Metody Diskret. Analiz. 3 (1964), 25–30. Google Scholar

[18] [18] Vizing, V. G., Critical graphs with given chromatic index (Russian). Metody Diskret. Analiz. 5 (1965), 9–17. Google Scholar

[19] [19] Waller, A. O., Simultaneously colouring the edges and faces of plane graphs. J.Combin. Theory Ser. B 69 (1997), 219–221. Google Scholar

Cité par Sources :