Geodesic
Minimax degrees of quasiplane graphs without $4$-faces
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 435-439 
O. V. Borodin; A. O. Ivanova; A. V. Kostochka; N. N. Sheikh. Minimax degrees of quasiplane graphs without $4$-faces. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 435-439. http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/
@article{SEMR_2007_4_a24,
     author = {O. V. Borodin and A. O. Ivanova and A. V. Kostochka and N. N. Sheikh},
     title = {Minimax degrees of quasiplane graphs without $4$-faces},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {435--439},
     year = {2007},
     volume = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
AU  - A. V. Kostochka
AU  - N. N. Sheikh
TI  - Minimax degrees of quasiplane graphs without $4$-faces
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2007
SP  - 435
EP  - 439
VL  - 4
UR  - http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/
LA  - en
ID  - SEMR_2007_4_a24
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%A A. V. Kostochka
%A N. N. Sheikh
%T Minimax degrees of quasiplane graphs without $4$-faces
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2007
%P 435-439
%V 4
%U http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/
%G en
%F SEMR_2007_4_a24

Voir la notice de l'article provenant de la source Math-Net.Ru

The $M$-degree of an edge $xy$ in a graph is the maximum of the degrees of $x$ and $y$. The minimax degree of a graph $G$ is the minimum over $M$-degrees of its edges. In order to get upper bounds on the game chromatic number, W. He et al showed that every planar graph $G$ without leaves and $4$-cycles has minimax degree at most $8$. This was improved by Borodin et al to the best possible bound $7$. Answering a question by D. West, we show that every plane graph $G$ without leaves and $4$-faces has minimax degree at most $15$. The bound is sharp. Similar results are obtained for graphs embeddable on the projective plane, torus and Klein bottle.

[1] H. L. Bodlaender, “On the complexity of some coloring games”, Internat. J. Found. Comput. Sci., 2 (1991), 133–147 | DOI | MR | Zbl

[2] O. V. Borodin, “Consistent colorings of graphs on the plane”, Diskret. Analiz, 45 (1987), 21–27 (in Russian) | MR | Zbl

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

[4] O. V. Borodin, “A generalization of Kotzig's theorem and prescribed edge coloring of plane graphs”, Math. Notes Acad. Sci. USSR, 48 (1990), 1186–1190 | DOI | MR | Zbl

[5] O. V. Borodin, A. V. Kostochka, N. Sheikh, and G. Yu, $M$-degrees of $C_4$-free planar graphs, submitted

[6] U. Faigle, U. Kern, H. A. Kierstead, and W. T. Trotter, “On the game chromatic number of some classes of graphs”, Ars Combin., 35 (1993), 143–150 | MR | Zbl

[7] B. Grünbaum, “New views on some old questions of combinatorial geometry”, Colloquio Internazionale sulle Teorie Combinatorie, v. I, Atti dei Convegni Lincei, 17, Accad. Nat. Lincei, Rome, 1976, 451–468 | MR

[8] W. He, X. Hou, K. W. Lih, J. Shao, W. Wang, and X. Zhu, “Edge-partitions of planar graphs and their game coloring numbers”, J. Graph Theory, 41 (2002), 307–317 | DOI | MR | Zbl

[9] A. Kotzig, “Contribution to the theory of eulerian polyhedra”, Mat. Čas., 5 (1955), 101–103 (in Russian) | MR

[10] A. Kotzig, “Contribution to the theory of Eulerian polyedra”, Mat. Čas., 13 (1963), 20–34 (in Russian) | MR

[11] P. Wernicke, “Uber den Kartographischen Vierfarbensatz”, Math. Ann., 58 (1904), 413–426 | DOI | MR | Zbl